What is recursion?
A function is a named block of code that does one job. Usually it calls other functions.
A recursive function calls itself. It solves a big problem by first solving a smaller copy of the same problem.
Example: the factorial n! = n × (n − 1) × … × 1. Notice that 5! = 5 × 4!. So to find fact(5), find fact(4) and multiply by 5.
def fact(n):
if n == 1: # base case
return 1
return n * fact(n - 1) # recursive case
Base case and recursive case
Every correct recursive function has two parts:
- Base case: the simplest input, answered directly with no more calls. For factorial, n = 1 (or n = 0) returns 1.
- Recursive case: the function calls itself with a smaller input, so each step moves toward the base case.
If either part is wrong, the function never stops. For example fact(n − 1) with no base case, or fact(n + 1) that moves away from it.
The call stack and stack frames
The computer keeps track of unfinished calls using the call stack. A stack works like a pile of plates: last in, first out.
Each call gets a stack frame. The frame stores its own parameters (like n), its local variables and the return address (where to continue after it finishes).
- fact(4) starts and waits for fact(3). Its frame stays on the stack.
- fact(3) waits for fact(2), which waits for fact(1).
- fact(1) hits the base case and returns 1. Its frame is popped.
- Each waiting frame now finishes its multiplication and is popped in turn.
Too many frames fill the stack's memory. The program crashes with a stack overflow (Python says RecursionError).
Tracing a recursive function
To trace, write each call on a new line, indented one level deeper. When a call returns, write its value and go back up.
power(2, 3)
power(2, 2)
power(2, 1)
power(2, 0) returns 1
returns 2 × 1 = 2
returns 2 × 2 = 4
returns 2 × 4 = 8A function that calls itself twice, like Fibonacci fib(n) = fib(n − 1) + fib(n − 2), makes a tree of calls. fib(5) calls fib(3) twice and fib(2) three times, so plain recursion repeats a lot of work. Storing answers you already found (memoisation) fixes this.
Recursive searching and sorting
Binary search on a sorted list: look at the middle item. If it is the target, stop (base case). If the target is smaller, search the left half; if bigger, the right half. An empty range is the other base case (not found). Each call halves the list, so a list of 1 000 items needs about 10 calls.
Merge sort: a list of 0 or 1 items is already sorted (base case). Otherwise split it in two halves, sort each half recursively, then merge the two sorted halves. This "divide and conquer" idea is behind many fast algorithms.
Recursion or a loop?
Anything done with recursion can also be done with a loop (iteration), and the reverse is also true.
- Recursion is shorter and clearer for problems that are naturally nested: trees, folders, divide-and-conquer, fractals.
- Loops use less memory (no pile of frames) and cannot overflow the stack.
Some languages (functional languages) use recursion as the main way to repeat.
Try it: the queue in class
Ask the last student in a line: "How many people are in front of you?" They do not count. They ask the person in front the same question and add 1 to the answer. The first person in line has no one in front and says 0 (the base case). The answers travel back down the line. Then write fact(n) or count(n) in Python and run it with n = 5. Compare with step 4 of the 3D.
Key formulas and definitions
- fact(n) = 1 if n = 1, else n × fact(n − 1)
- fib(n) = n if n < 2, else fib(n − 1) + fib(n − 2)
- sum(list) = 0 if empty, else first + sum(rest)
- Binary search: about log₂(n) calls for n items
- Stack depth of fact(n) = n frames
Worked examples
1. Write a recursive function to add the numbers 1 to n.
Base case: n = 0 → return 0. Recursive case: return n + total(n − 1). <pre>def total(n): if n == 0: return 0 return n + total(n - 1)</pre>total(4) = 4 + 3 + 2 + 1 + 0 = 10.
2. Trace fact(3) and show the stack.
Calls: fact(3) → fact(2) → fact(1). Stack at its tallest: fact(1) on top of fact(2) on top of fact(3). Returns: fact(1) = 1, fact(2) = 2 × 1 = 2, fact(3) = 3 × 2 = 6.
3. What is wrong with: def f(n): return n * f(n - 1)
There is no base case. f(3) calls f(2), f(1), f(0), f(−1)… forever. Python stops it with RecursionError (stack overflow). Add: if n <= 1: return 1.
4. Write a recursive function that reverses a string.
Base case: empty string returns itself. Otherwise take the last character plus the reverse of the rest. <pre>def rev(s): if s == "": return "" return s[-1] + rev(s[:-1])</pre>rev("cat") = "t" + rev("ca") = "t" + "a" + rev("c") = "tac".
5. How many calls does fib(4) make in total (plain recursion)?
fib(4) → fib(3), fib(2). fib(3) → fib(2), fib(1). Each fib(2) → fib(1), fib(0). Count: fib(4) 1, fib(3) 1, fib(2) 2, fib(1) 3, fib(0) 2 = 9 calls.
6. Binary search for 23 in [3, 8, 15, 23, 42, 57, 61]. Show each call.
Call 1: middle is 23 at index 3. Found in 1 call. Search for 57: call 1 middle 23 < 57 → right half [42, 57, 61]; call 2 middle 57 → found. 2 calls.
Common mistakes
- Forgetting the base case, so the function never stops and causes a stack overflow.
- Writing a recursive case that does not get smaller, e.g. calling f(n) again instead of f(n − 1).
- Calling the function but not returning its result: writing fact(n − 1) instead of return n * fact(n − 1).
- Thinking all calls run at the same time. They wait in order on the stack; the last one called finishes first.