Programming techniques: Recursion

Overview

Recall questions on recursive subroutines, base and general cases, tracing factorial calls, the call stack and unwinding, stack overflow, recursion depth on large data, recursion compared with iteration, and slow recursive Fibonacci.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What makes a subroutine recursive, and what two parts must it always have?

   Model answer

   It is recursive if it calls itself. It must have a base case — a condition under which it returns an answer directly, without calling itself — and a general case, in which it calls itself with a smaller or simpler version of the problem. The general case must move the problem towards the base case, so that the chain of calls is guaranteed to reach it and start returning.

2. 2

   What actually goes wrong if you forget the base case?

   Model answer

   The subroutine calls itself forever, and unlike an infinite while loop it consumes memory as it goes. Every call pushes a new frame onto the call stack, holding the return address, the parameters and that call's local variables, and because no call ever returns, no frame is ever removed. The stack grows until the memory reserved for it is exhausted and the program crashes with a stack overflow. It usually happens within a fraction of a second, so the symptom is an immediate crash rather than a hang.

3. 3

   Is having a base case enough to guarantee that a recursive subroutine will stop?

   Model answer

   No. The general case must also move towards the base case on every call. A factorial routine whose base case is n == 0 and whose general case returns n * factorial(n - 1) is fine for positive n, but called with -1 it goes -1, -2, -3 and so on, moving away from 0 forever, and still overflows the stack. Two conditions are needed: a base case exists, and every recursive call brings the argument nearer to it.

4. 4

   Trace this by hand for factorial(4). What value comes back, and in what order do the calls finish? function factorial(n) if n == 0 then return 1 else return n * factorial(n - 1) endif endfunction

   Model answer

   It returns 24. On the way down, factorial(4) cannot finish until it knows factorial(3); factorial(3) waits on factorial(2); factorial(2) waits on factorial(1); factorial(1) waits on factorial(0); factorial(0) meets the base case and returns 1 immediately. On the way back up, the calls finish in the reverse order to the order they were made: factorial(1) = 1 * 1 = 1, factorial(2) = 2 * 1 = 2, factorial(3) = 3 * 2 = 6, factorial(4) = 4 * 6 = 24. At the deepest point five calls are outstanding at once, each waiting for the one below it.

5. 5

   Describe what is on the call stack while a recursive routine runs, and what is meant by the stack 'unwinding'.

   Model answer

   Each call pushes a stack frame containing the return address (the point to carry on from when this call finishes), the parameter values passed in, and that call's own local variables. The frames pile up as the recursion goes deeper, so at the deepest point there is one frame for every level and each frame's values are kept separate from the others. Once the base case returns a value, its frame is popped and control returns to the frame beneath, which can now complete its own calculation and return in turn. That popping back up, one frame at a time, is the unwinding. The stack only begins to shrink after the base case is reached.

6. 6

   What is a stack overflow, and give two different causes.

   Model answer

   The call stack is given a limited region of memory. A stack overflow occurs when frames are pushed onto it faster than they are popped off, until that space is used up, at which point the program crashes. One cause is recursion with a missing or unreachable base case, so calls never return at all. The other is recursion that is entirely correct but simply goes too deep for the stack — a recursive routine that steps through a list of a million items will overflow even though it works perfectly on a test list of ten. The second kind is dangerous because it passes testing and fails on real data.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.