Counting calls: slow, memoised, loop
The same answer, 610, with 1973 calls versus 29. The memoised version also handles fib(80).
A recursive function solves a problem by calling itself on a smaller version of the same problem, until it reaches a base case it can answer directly. Python allows it, but caps the depth (about 1000 calls by default) and has no tail-call optimisation, so deep problems are usually written as loops.
Change the code and press Run (Ctrl+Enter). Predict what will happen first, then break it on purpose and read what changes. Your edits are saved and match the lesson page.
Ready for more? This phase has 6 hands-on exercises with automatic checks.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Write a recursive power(base, exponent) for whole-number exponents of 0 or more, where power(2, 0) is 1. Print power(2, 10).
Write a recursive sum_list(items) that returns the sum of a list. The base case is the empty list. Print sum_list([3, 4, 5]).
Write a recursive flatten(items) that turns a list nested to any depth, such as [1, [2, [3, 4]], 5], into one flat list [1, 2, 3, 4, 5]. Test it on [] and on [[], [[]]] too. Then say why count_down(5000), a recursive function that makes the list [5000, 4999, ..., 1] one call per number, would fail with the default limit while flatten on real data would not.
Explain it without notes
What are the base case and the recursive case? What goes wrong if either is missing?
Describe what the call stack looks like for factorial(3).
Why does Python raise RecursionError, and what are your options?
How does memoisation speed up Fibonacci?
When should you choose a loop over recursion in Python?
Expected output
610 with 1973 calls
610 with 29 calls
23416728348467685
5050