Show awareness of what a compiler has to do to translate recursive programming code

19.2 Recursion – How a Compiler Turns Recursive Code into Machine Instructions

int factorial(int n) {
    if (n == 0) return 1;          // base case
    return n * factorial(n - 1);   // recursive call
}

Why Does a Compiler Care About Recursion?

A compiler must translate the high‑level recursive calls into low‑level machine code that the CPU can execute. This involves:

• Creating a call stack to keep track of each function invocation.
• Allocating space for local variables and return addresses.
• Ensuring that the base case stops the recursion to avoid infinite loops.
• Optimising tail‑recursive calls to prevent stack overflow.

Compiler Pipeline for Recursive Functions

1. Lexical Analysis – Breaks source code into tokens.
2. Syntax Analysis – Builds an abstract syntax tree (AST).
3. Semantic Analysis – Checks types, scopes, and ensures the recursion is well‑formed.
4. Intermediate Representation (IR) – Translates the AST into a lower‑level form (e.g., three‑address code).
5. Optimization – Detects tail recursion and may convert it to a loop.
6. Code Generation – Emits machine code or bytecode, handling stack frame layout.

How a Recursive Call is Implemented at Runtime

When factorial(3) is called, the stack grows like this:

1. Call factorial(3) → push frame with n=3.
2. Inside, call factorial(2) → push new frame.
3. Repeat until factorial(0) → base case, return 1.
4. Unwind: each frame multiplies its n by the result from the deeper call.

Tail Recursion & Compiler Optimisation

Tail recursion occurs when the recursive call is the last action in the function:

int sumTail(int n, int acc) {
    if (n == 0) return acc;
    return sumTail(n - 1, acc + n);  // tail call
}

A compiler can transform this into a loop, eliminating the need for new stack frames and preventing stack overflow.

Exam Tip Box