Lesson 20 · Algorithms

Recursion

A recursive function solves a problem by calling itself on a smaller copy of the same problem, until it reaches a case small enough to answer straight away. Follow fact(4) as Python stacks up one call frame per waiting call, hits the base case, then unwinds with return values. Then see Python's depth limit, the loop alternative, and why naive Fibonacci repeats work.

10 min12 steps5 questionsIntermediate

Fig 20 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01What stops fact(n) from calling itself forever?

The base case is a problem small enough to answer directly. Each call makes n 1 smaller, so the calls always reach it, and then they stop.

02While fact(4) is running, at its deepest point, how many frames of fact are on the call stack?

fact(4), fact(3), fact(2) and fact(1) are all running at once: three of them are waiting for the call above. That is four frames.

03Which call of fact finishes first?

The call stack is last in, first out. fact(1) started last and returns first; then fact(2), fact(3) and finally fact(4) finish.

04In a fresh Python, what does sys.getrecursionlimit() return, and what happens if calls go deeper?

The default limit is 1000. Going past it, for example with a missing base case, raises RecursionError: maximum recursion depth exceeded.

05Why is the plain recursive fib(n) slow?

Each call calls fib twice, so the same values are recomputed: fib(2) three times, fib(1) five times. Storing each answer once is dynamic programming.

Key terms

Glossary

Recursion: When a function calls itself to solve a smaller copy of the same problem.
Base case: The input small enough to answer directly, without another call. It is what stops the recursion.
Recursive case: The part of the function that calls itself on a smaller input, such as n * fact(n - 1).
Call frame: The scratch space Python makes for one call of a function, holding that call's own variables, like n.
Call stack: The pile of frames for calls still running. The newest is on top, and it is the first to finish.
Unwinding: The calls finishing one by one, each handing its return value to the call below it.
RecursionError: The error Python raises when calls go deeper than the recursion limit (1000 by default).

Fine print

Notes and sources

The drawing shows one block for each call of fact that is still running, stacked in the order the calls started. In CPython every call gets its own frame object; when the call returns, the frame is released.
The depth shown counts only fact’s frames. The code that called fact(4) runs in a frame too, so Python’s own count is a little higher, which is why fact(999) still works in a fresh python3 -c run and fact(1000) does not.
The limit protects Python itself from running out of memory for its stack. sys.setrecursionlimit can raise it, with care: too high a limit can crash the interpreter.
Here the base case is n <= 1, so fact(1) and fact(0) both answer 1 without calling again.
In fib, fib(0) and fib(1) are the base cases. With functools.cache, fib(n) for each n is worked out once and then looked up.

Quiz Unlocks after the last step.