How recursion uses stack

A recursive function calls itself. Every call creates an activation record (stack frame) holding the parameters, local variables and the return address. These frames are pushed on the system call stack when a function is called and popped when it returns. Because the last call to start is the first to finish (LIFO), the stack stores the pending work and intermediate results of each call.

Example: factorial

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

Calling fact(3):

Winding phase (calls, frames pushed)

 step1       step2       step3       step4
|       |   |       |   |       |   |fact(0)|
|       |   |       |   |fact(1)|   |fact(1)|
|       |   |fact(2)|   |fact(2)|   |fact(2)|
|fact(3)|   |fact(3)|   |fact(3)|   |fact(3)|
+-------+   +-------+   +-------+   +-------+

Each frame holds its own n and waits for the result of the call above it. The call fact(0) meets the base case and returns 1.

Unwinding phase (returns, frames popped)

Result: fact(3) = 6.

Another example is Fibonacci, where the stack holds the pending fib(n-2) calls while fib(n-1) is being computed. Maximum stack depth equals the depth of recursion (n + 1 frames for factorial), so very deep recursion may cause stack overflow. Without the stack the function could not remember where to resume or the partial products, which is why recursion needs a stack (and why any recursive algorithm can be made iterative by using an explicit stack).