Recursion in Python
Implement factorial and Fibonacci recursively, add print traces to see the call sequence, and learn about Python's recursion limit.
- Implement factorial recursively in Python
- Implement Fibonacci recursively in Python
- Understand Python's recursion limit and how to query it
The concepts are clearer once you can watch them happen. The <Runnable> block
below implements two classic recursive functions and prints a trace for
factorial so you can follow the call sequence step by step.
Factorial and Fibonacci
Reading the trace
Each line of the factorial trace shows the call going deeper (increasing
indentation) and then unwinding (decreasing indentation as results are returned).
Notice the base case fires once — at factorial(1) — and every other call waits
for its inner call before it can compute its own result.
This is the stack at work. When factorial(5) calls factorial(4), the frame
for factorial(5) is paused and pushed onto the stack. It resumes only after
factorial(4) completes and pops off.
Fibonacci: correct but slow
The recursive Fibonacci is famously inefficient. fib(5) calls fib(4) and
fib(3). fib(4) calls fib(3) and fib(2). fib(3) is computed twice,
fib(2) three times, and so on — the number of calls grows exponentially. For
small n (say, under 30) this is fine. For large n it is not.
The fix — memoisation (caching results so each subproblem is computed only once) or an iterative approach — is an optimisation you'd add after getting it correct. This is step 4 of the problem-solving process.
sys.getrecursionlimit() returns Python's current recursion depth limit
(typically 1 000). You can raise it with sys.setrecursionlimit(n), but
that is almost always a sign the algorithm should be iterative instead of
recursive. A genuine need for recursion depths above a few hundred is rare.
Where to go next
Next: search concepts — linear search and binary search, and why binary search is so much faster on sorted data.
Recursion concepts
Understand recursion as a function calling itself on a smaller sub-problem, and learn to identify the base case and recursive case that every correct recursive function needs.
Search concepts
Linear search scans every element — O(n). Binary search halves the search space each step — O(log n). The catch is that binary search only works on sorted data.