A recursive subroutine is one that calls itself. Recursion solves a problem by reducing it to a smaller version of the same problem, until it reaches one simple enough to answer directly.

Base case and general case

Every correct recursive function has two parts:

  • Base case: a situation where it returns an answer without calling itself. It stops the recursion.
  • General (recursive) case: it calls itself with a smaller or simpler input that moves towards the base case.

Without a base case, or if the input never gets closer to it, the calls never stop and the program crashes with a stack overflow.

Factorial: n! = n x (n-1)!, with 0! = 1.

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
  IF n = 0 THEN
    RETURN 1
  ELSE
    RETURN n * Factorial(n - 1)
  ENDIF
ENDFUNCTION

Tracing Factorial(3):

Factorial(3) = 3 * Factorial(2)
             = 3 * (2 * Factorial(1))
             = 3 * (2 * (1 * Factorial(0)))
             = 3 * 2 * 1 * 1 = 6

The call stack

Each call gets a stack frame holding its parameters, local variables and return address. Calls are pushed on the stack as they go deeper (winding), and popped as each returns a value (unwinding). Deep recursion uses a lot of memory.

More examples

Fibonacci: each number is the sum of the previous two.

FUNCTION Fib(n : INTEGER) RETURNS INTEGER
  IF n <= 1 THEN
    RETURN n
  ELSE
    RETURN Fib(n - 1) + Fib(n - 2)
  ENDIF
ENDFUNCTION

This is easy to write but slow, as it repeats the same calculations many times.

Recursion suits problems that are naturally self-similar: tree traversals, binary search, merge sort, quicksort and the Towers of Hanoi.

Recursion versus iteration

Feature Recursion Iteration
Code Short, elegant Often longer
Memory Uses stack frames Uses little
Speed Slower (call overhead) Faster
Risk Stack overflow Infinite loop

Any recursive solution can be rewritten with loops and an explicit stack, and any loop can be written recursively. Choose recursion when it makes the problem clearer.

Check your understanding

What is the purpose of a base case?

  • To stop the recursion
  • To start the program
  • To declare variables
  • To loop forever

Answer: To stop the recursion. It returns a result without another call.

What happens if a recursive function has no reachable base case?

  • It returns 0
  • Stack overflow
  • It runs once
  • It sorts the data

Answer: Stack overflow. The call stack fills up.

What is Factorial(4)?

  • 10
  • 16
  • 24
  • 12

Answer: 24. 4 x 3 x 2 x 1 = 24.

Where are return addresses and parameters stored during recursion?

  • In the call stack as stack frames
  • In the hard disk
  • In the ALU
  • In ROM

Answer: In the call stack as stack frames. They are removed as calls return.