Recursion

Recursion is a technique where a routine (a function or procedure) calls itself to solve a problem. Each call works on a smaller version of the same problem until it becomes simple enough to answer directly.

Every valid recursive routine has two essential features:

Feature	What it does
Base case	The stopping condition. It returns a value without calling the routine again, so the recursion ends.
General case (recursive case)	The routine calls itself, with an argument that moves toward the base case (the problem gets smaller).

Both are needed. Without a base case (or one that can never be reached), the routine calls itself forever — this is infinite recursion, and it will crash the program (see §5).

Think of it like a set of nesting dolls: you keep opening a smaller doll (general case) until you reach the tiny solid one that cannot be opened (base case).

In Cambridge pseudocode a recursive routine is written like any FUNCTION or PROCEDURE, but its body contains a call to itself. The standard shape uses IF … THEN … ELSE so exactly one branch runs per call.

The classic example — factorial (n! = n × (n−1) × … × 1, and 0! = 1):

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

Read it as: if we have reached 0, the answer is 1; otherwise the answer is n times the factorial of one less.

A countdown procedure shows recursion without a return value:

PROCEDURE Countdown(n : INTEGER)
    IF n = 0 THEN
        OUTPUT "Liftoff"
    ELSE
        OUTPUT n
        Countdown(n - 1)
    ENDIF
ENDPROCEDURE

Recipe for writing any recursive routine:

1. Identify the base case — the simplest input and its direct answer.
2. Identify the general case — express the answer using the routine called on a smaller argument.
3. Make sure the argument in the recursive call (here, n - 1) moves toward the base case.

Remember the operators: <- is assignment, comparison uses =, <>, <, >, <=, >=.

When a routine calls itself, the current call cannot finish until the inner call returns. The system keeps track of every paused call on the call stack, pushing a new stack frame for each one.

Winding (building up): Frames are pushed as the calls are made, until the base case is reached.

Unwinding: The base case returns a value; then each frame is popped in turn, passing its result back up to the call below it.

Trace of Factorial(3): the calls wind down to Factorial(0) (which returns 1), then the multiplications happen on the way back up — innermost first:

F(0) returns 1 F(1) = 1 × 1 = 1 F(2) = 2 × 1 = 2 F(3) = 3 × 2 = 6 Result = 6

So Factorial(3) = 3 × 2 × 1 = 6. Notice the order: the calls go down to the base case first, and the actual multiplications happen on the way back up as the stack unwinds.

How to trace in an exam:

1. Write each call, noting it is waiting for the inner call (winding).
2. Reach the base case and write its returned value.
3. Substitute that value back into the call above, working upward, until the first call returns (unwinding).

Anything you can do with recursion you can also do with iteration (a loop), and vice versa — so how do you choose?

Recursion is beneficial when the problem is naturally self-similar — it is defined in terms of smaller copies of itself. Classic cases:

• Tree traversal — e.g. visiting every node of a binary tree (each subtree is itself a tree).
• Divide-and-conquer — e.g. binary search, merge sort, where each step splits the problem into smaller sub-problems.

For these, the recursive code is shorter, clearer and closer to the definition of the problem, so it is easier to write and to understand.

Iteration may be preferred when:

• Memory is limited or the depth could be very large. A loop uses a constant amount of extra memory, whereas recursion pushes a new stack frame for every call, so it uses memory proportional to its depth and risks a stack overflow.
• Speed matters. Function calls have an overhead (pushing/popping frames), so deep recursion can be slower than the equivalent loop.

	Recursion	Iteration
Code	Shorter, matches self-similar problems	Can be longer for self-similar problems
Memory	One stack frame per call (grows with depth)	Constant extra memory
Risk	Stack overflow if too deep	No stack overflow

Rule of thumb: choose recursion for clarity on self-similar/recursive data; choose iteration for efficiency and safety on large or deep inputs.

To run a recursive routine, the compiler/run-time system uses the call stack — exactly the same mechanism it uses for ordinary subroutine calls, just used many times over.

For every call, a stack frame is pushed onto the call stack. The frame stores:

• the return address — where in the program to carry on once this call finishes;
• the call's parameters and local variables — so each call keeps its own separate copy (this is why each level of Factorial 'remembers' its own n).

Winding: as the recursive calls are made, frames are pushed one on top of another until the base case returns a value.

Unwinding: the system then unwinds the recursion — as each call completes, its frame is popped off the stack and control jumps to the return address stored in the frame below it, carrying the returned value with it. This repeats until the first call returns its result.

Stack overflow. The call stack is a fixed, finite region of memory. If the recursion is too deep — most often because the base case is never reached (infinite recursion), or simply because the depth is enormous — frames keep being pushed until there is no space left. The result is a stack overflow and the program crashes.

This is the key practical difference from iteration: a loop reuses one set of local variables, so it never grows the stack; recursion adds a frame per call.