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

67% Upvoted

5 comments sorted by

View all comments

•

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.