Recursion

What recursion is

Recursion is when a subroutine calls itself to solve a problem by breaking it into smaller versions of the same problem. Every recursive solution must have:

• a base case — a condition that stops the recursion (no further calls);
• a general (recursive) case — where the routine calls itself with a smaller/simpler input, moving towards the base case.

Without a base case, the routine calls itself forever, filling the call stack until a stack overflow error occurs.

Example — factorial

function factorial(n)
   if n == 0 then          // base case
      return 1
   else                    // general case
      return n * factorial(n - 1)
   endif
endfunction

factorial(3) → 3 × factorial(2) → 3 × 2 × factorial(1) → 3 × 2 × 1 × factorial(0) → 3 × 2 × 1 × 1 = 6.

The call stack

Each recursive call is pushed onto the stack, storing its parameters and return address. When the base case is reached, the calls return in reverse order (the stack unwinds), combining results. This is why deep recursion uses a lot of memory.

Recursion vs iteration

	Recursion	Iteration
Approach	Function calls itself	Loops (for/while)
Memory	More (stack frames)	Less
Readability	Elegant for naturally recursive problems (trees, divide-and-conquer)	Simpler for straightforward repetition
Risk	Stack overflow	Infinite loop

Any recursive algorithm can be rewritten iteratively (often using an explicit stack), and vice versa.

Where recursion shines

• Traversing trees and graphs.
• Divide-and-conquer algorithms (merge sort, quicksort, binary search).
• Problems defined recursively (factorial, Fibonacci, Towers of Hanoi).

Worked example

What are the base case and general case of a recursive routine that sums 1 to n?

• Base case: if n == 0 return 0.
• General case: return n + sum(n − 1). Each call reduces n by 1 until it hits 0. ✓

Common mistakes

• Missing or unreachable base case → infinite recursion → stack overflow.
• The general case not moving towards the base case (input not shrinking).
• Forgetting that recursion uses more memory than iteration (stack frames).

Exam tips

• Always identify the base case and general case in any recursive routine.
• Be able to trace a recursive call, showing the stack building up then unwinding.
• Compare recursion and iteration on memory and suitability.

Key facts to remember

• Recursion = a routine calling itself, needing a base case (stops) and a general case (calls itself with a smaller input).
• Calls are stored on the stack; too deep → stack overflow; it uses more memory than iteration.
• Ideal for trees/graphs and divide-and-conquer; any recursion can be written iteratively.