AlgorithmsAlgorithmsCollege

Recursion

Base cases, recursive cases and recurrence relations.

A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case that is answered directly and a recursive case that moves toward it. Factorial is the classic example: $n! = n \times (n - 1)!$ , with $0! = 1$ as the base case.

Recursion fits problems with self-similar structure, such as trees, nested folders, divide-and-conquer sorts and many puzzles. Each call waits on the call stack until the smaller call returns, so very deep recursion can overflow the stack, and naive recursion can repeat work, which memoisation fixes.

Key ideas

Always define the base case first and make sure every call moves toward it.
Trace with a call tree to see the order of calls and returns.
Recurrences describe cost: $T(n) = T(n - 1) + O(1)$ gives $O(n)$ ; $T(n) = 2T(n/2) + O(n)$ gives $O(n \log n)$ .
Naive Fibonacci is exponential; memoised Fibonacci is linear.

Worked example

Trace `f(n) = n == 0 ? 0 : n + f(n - 1)` for `f(4)`.

$f(4) = 4 + f(3)$ .
$f(3) = 3 + f(2)$ , $f(2) = 2 + f(1)$ , $f(1) = 1 + f(0)$ .
Base case: $f(0) = 0$ .
Unwind: $f(1) = 1$ , $f(2) = 3$ , $f(3) = 6$ , $f(4) = 10$ .

Answer: $10$

Common mistakes

Missing or unreachable base case, causing infinite recursion.
Recursive calls that do not shrink the problem.
Ignoring repeated work in tree-shaped recursion.

Practice questions

Try each one, then open the answer. Numerical answers on this page are verified by an automated calculation check.

1.Compute $5!$ recursively.
Show answer
$120$
2.Fibonacci with $F(0) = 0$ , $F(1) = 1$ : find $F(10)$ .
Show answer
$55$
3.How many moves does Tower of Hanoi need for 5 discs ( $2^n - 1$ )?
Show answer
$31$

Key ideas

Worked example

Common mistakes

Practice questions

More in Algorithms