Recursion Basics
Recursion is when a function calls itself to solve smaller instances of the same problem.
5 CALLS
DESCEND
factorial(5) cannot answer yet: it needs factorial(4). Push a frame and defer.
Next
factorial(4) cannot answer yet: it needs factorial(3). Push a frame and defer.
Function
N
Intuition
Recursion is solving a problem by breaking it down into smaller versions of itself. It's like looking into parallel mirrors!
Concept
- Base Case: The condition to stop recursion (e.g., n=1). Without this, you get infinite recursion (Stack Overflow).
- Recursive Case: The part where the function calls itself with a smaller input.
- Call Stack: The computer uses a stack to keep track of function calls.
How it Works
Factorial(n): n * factorial(n-1)
Fibonacci(n): fib(n-1) + fib(n-2)
Notice how Fibonacci creates a tree of calls, often recalculating the same values (overlapping subproblems). This is why simple recursion can be slow (O(2^n))!
Step-by-Step Breakdown
Watch the visualization:
- Factorial: Linear stack growth O(N).
- Fibonacci: Exponential tree growth O(2^N).
Trace: fib(5) with no cache
fib(5)
The root. It needs fib(4) and fib(3), and nothing is remembered between the two branches.
1 call
fib(4)
Reached once, from the root. It needs fib(3) and fib(2).
1 call
fib(3)
Reached from fib(5) and again from fib(4). The second visit repeats the first exactly.
2 calls
fib(2)
Reached from fib(4) and from both copies of fib(3).
3 calls
fib(1)
A base case, returned five separate times.
5 calls
fib(0)
The other base case, returned three separate times.
3 calls
total
Fifteen calls to produce fib(5) = 5, across only six distinct arguments. Storing each result the first time it is computed removes every repeat, which turns the exponential tree into a linear walk.
15 calls
When to Use
- Tree/Graph traversals (DFS).
- Divide and Conquer algorithms (Merge Sort, Quick Sort).
- When the problem has a recursive structure.
When NOT to Use
- When stack space is limited (risk of overflow).
- When simple iteration is much more efficient.
How to Identify
"Compute nth...", "Tree structure", "Subproblems".
Applying for software engineering roles? Free, no sign-up: