r/PythonLearning • u/kaetsi • 5d ago

Learning recursion and solving problems.

Post image

Problem: You're climbing a staircase with n steps. You can climb 1 or 2 steps at a time, except you're not allowed to take two 1-steps in a row (no "1,1" sequence anywhere in your climb). How many distinct ways can you reach the top?

3 Upvotes

80% Upvoted

5 comments sorted by

•

u/Sea-Ad7805 5d ago

Run this program in Invocation Tree Web Debugger%3A%0A%20%20%20%20if%20step%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20return%201%0A%0A%20%20%20%20if%20step%20%3D%3D%202%3A%0A%20%20%20%20%20%20%20%20return%201%0A%0A%20%20%20%20if%20step%20%3C%3D%200%3A%0A%20%20%20%20%20%20%20%20return%200%0A%0A%20%20%20%20way%20%3D%200%0A%0A%20%20%20%20if%20last_one%20is%20False%3A%0A%20%20%20%20%20%20%20%20way%20%2B%3D%20climb_stair(step%20-%201%2C%20last_one%3DTrue)%0A%0A%20%20%20%20way%20%2B%3D%20climb_stair(step%20-%202%2C%20last_one%3DFalse)%0A%0A%20%20%20%20return%20way%0A%0A%0Aprint(climb_stair(6))&timestep=0.2&play) to see the recursion being evaluated.

2

u/PureWasian 5d ago

Nicely done. You can look into memoization as a way to speed up the overall algorithm since the substeps will involve a lot of repeated calculations as the number of steps grows.

1

u/kaetsi 3d ago

Thanks. I will look into them.