MediumPython ProgrammingHigh School (9–10)High School (11–12)UndergraduateGeneralPython Essentials › RecursionConceptual
A staircase has n steps. You climb one step or two steps at a time.
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
A staircase has n steps. You climb one step or two steps at a time. In how many different ways can you reach the top? Write a recursive function with a memory, and find the answer for 1, 2, 3, 4, 5 and 30 steps.
The worked solution
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Ask the four questions.
- The smaller problem: a staircase with fewer steps.
- The base case: 1 step has 1 way. 2 steps have 2 ways (1+1, or 2).
- The step: the last move was one step (from step
n - 1) or two steps (from stepn - 2). So the ways to reachnare the ways to reachn - 1, plus the ways to reachn - 2. - Closer: yes.
This is the Fibonacci rule, with different starting values. So it needs a memory, or it would be far too slow for 30.
Check. For 3 steps: (1,1,1), (1,2), (2,1), which is 3 ways. For 4: 5. For 5: 8.
Answer: 1, 2, 3, 5, 8 and 1 346 269 ways.
Discussion (0)
Log in to join the discussion.
Loading…