MediumPython ProgrammingHigh School (9–10)High School (11–12)UndergraduateGeneralPython Essentials › RecursionConceptual
For sum_to(3), where sum_to(n) is 0 for n == 0 and n + sum_to(n - 1) otherwise, write the calls…
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
For sum_to(3), where sum_to(n) is 0 for n == 0 and n + sum_to(n - 1) otherwise, write the calls that are waiting at each moment, and the value that each call gives back.
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. Go down to the base case, and then come back up.
Going down:
sum_to(3)is called. It needssum_to(2), so it waits.sum_to(2)is called. It needssum_to(1), so it waits.sum_to(1)is called. It needssum_to(0), so it waits.sum_to(0)is called. This is the base case.
Coming back up:
| Call | Gives back |
|---|---|
sum_to(0) | 0 |
sum_to(1) | 1 + 0 = 1 |
sum_to(2) | 2 + 1 = 3 |
sum_to(3) | 3 + 3 = 6 |
At the deepest moment, four calls are waiting or running: sum_to(0) on top of sum_to(1), sum_to(2) and sum_to(3).
Check. 1 + 2 + 3 is 6.
Answer: The calls give back 0, 1, 3 and 6, and the first call gives 6.
Discussion (0)
Log in to join the discussion.
Loading…