EasyPython ProgrammingHigh School (9–10)High School (11–12)UndergraduateGeneralPython Essentials › RecursionConceptual
For each function, say whether a memory (a dictionary of answers) would help, and why.
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
For each function, say whether a memory (a dictionary of answers) would help, and why.
factorial(n), for one value ofn.fibonacci(n), the simple recursive version.- A function that gives the current time.
power(base, exponent)called many times with the same two numbers.- A function that counts the paths in a grid, where each cell asks for the cell above and the cell to the left.
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. A memory helps when the same smaller problem comes again and again, and the answer does not change.
- No. Each smaller factorial is asked for once. There is nothing to remember.
- Yes, a lot. The same small values are worked out again and again.
- Never. The answer changes with the time. An old answer would be wrong.
- Yes, if the same numbers come again. The second call can use the answer of the first. (It helps with calls from outside, not inside the recursion.)
- Yes. Two cells can ask for the same cell, so the same value is worked out many times, as in Fibonacci.
Check. For each, ask two questions: does the same input come again? Does the same input always give the same answer?
Answer: no, yes, never, yes, yes.
Discussion (0)
Log in to join the discussion.
Loading…