Recursion: short notes (Programming in C)

Introduction

A function is recursive when it calls itself, directly or through other functions. Recursion expresses a problem in terms of smaller instances of the same problem: the factorial of $n$ is $n$ times the factorial of $n-1$ ; a binary tree is a root with two smaller binary trees. The working task is to take a short recursive C function and find its output, its return value, or how many calls it makes.

This note covers how recursion executes, the main forms of recursion, and standard examples with their costs. The companion note Recursion Tracing and Call Counting gives systematic methods for tracing.

Conventions: C11, hosted; outputs are for gcc on x86-64 Linux.

Prerequisites

Functions and Parameter Passing: call by value, return values.
Control Flow: if, return.

Core concepts

Base case and recursive case

Every correct recursive function has:

One or more base cases, answered without a recursive call.
A recursive case that calls the function on an argument closer to a base case under some measure (smaller $n$ , shorter list, smaller subtree).

C

/* Domain: n >= 0; all intermediate products must fit long; sufficient stack. */
long fact(int n) {
    if (n <= 1) return 1;          /* base case */
    return n * fact(n - 1);        /* recursive case: n decreases */
}

A missing or unreachable base case gives unbounded recursion. In practice this exhausts the call stack and the program crashes; the C standard sets no recursion limit, and the failure mode is outside the language.

How a recursive call executes

Each call, recursive or not, gets its own activation record (stack frame) holding its parameters, automatic variables and the return address. A recursive call does not overwrite the caller's n; it creates a new n.

Figure 1. Recursion tree of fib(5): each node is one call, children are the calls it makes, and leaves are base cases fib(1) and fib(0). The tree has 15 nodes. The call stack at any moment is one root-to-node path.

The recursion depth is the largest number of frames active at once, the height of the recursion tree plus one. Space is proportional to depth only when each frame has constant-sized local/auxiliary storage. Generally sum frame-local and allocated auxiliary storage over simultaneously live calls; call count alone also does not determine time when work per call varies.
The total number of calls equals the number of nodes in the recursion tree, and governs the running time.
Calls are winding (going down) until a base case returns; then the frames unwind in last-in first-out order. This is why recursion can always be simulated with an explicit stack.

For sum(n) = n + sum(n - 1) with sum(0) = 0, the call sum(100) returns 5050 with a maximum depth of 101 frames (sum(100) down to sum(0)).

Forms of recursion

Form	Definition	Example
Direct	`f` calls `f`	`fact`
Indirect (mutual)	`f` calls `g`, `g` calls `f`	`is_even` and `is_odd`
Linear	at most one recursive call per activation	`fact`, `sum`
Tree (multiple)	two or more recursive calls per activation	`fib`, Tower of Hanoi
Tail	the recursive call is the last action; its result is returned unchanged	`gcd`, `fact_acc`
Non-tail	work remains after the call returns	`fact` (multiplies after returning)
Nested	an argument is itself a recursive call	Ackermann: `A(m-1, A(m, n-1))`

Mutual recursion example:

C

int is_even(int n);                                   /* declaration needed first */
/* Both parity routines require n >= 0 and sufficient stack. */
int is_odd(int n)  { return n == 0 ? 0 : is_even(n - 1); }
int is_even(int n) { return n == 0 ? 1 : is_odd(n - 1); }

is_even(10) is 1 and is_odd(7) is 1.

Tail recursion and accumulators

A non-tail function can often be made tail recursive by carrying the pending work in an accumulator parameter:

C

long fact_acc(int n, long acc) {           /* call as fact_acc(n, 1) */
    return n <= 1 ? acc : fact_acc(n - 1, acc * n);
}

A tail call can be replaced by a jump back to the start of the function with updated parameters, which is exactly a loop. Compilers often perform this optimisation, but C does not require it, so a tail recursive C function may still use $O(n)$ stack.

Order of work: before or after the call

Where the output statement sits relative to the recursive call decides the order:

C

/* down/up require n >= 0 and sufficient stack. */
void down(int n) { if (n == 0) return; printf("%d ", n); down(n - 1); }  /* 4 3 2 1 */
void up(int n)   { if (n == 0) return; up(n - 1); printf("%d ", n); }    /* 1 2 3 4 */

Work done before the call happens while winding (in call order); work done after happens while unwinding (in reverse order). The same idea separates preorder and postorder tree traversals.

How it works: costs of standard recursions

The number of calls $C(n)$ and the running time $T(n)$ satisfy recurrences read directly from the code.

Function	Recurrence for calls	Calls / time	Depth
`fact(n)`, `sum(n)`	$C(n) = C(n-1) + 1$	$\Theta(n)$	$\Theta(n)$
`fib(n)` naive	$C(n) = C(n-1) + C(n-2) + 1$ , $C(0)=C(1)=1$	$2F_{n+1} - 1 = \Theta(\varphi^n)$	$\Theta(n)$
`power(x, n)` by halving	$C(n) = C(\lfloor n/2 \rfloor) + 1$ , $C(0)=1$	$\lfloor \lg n \rfloor + 2$ for $n \ge 1$	$\Theta(\lg n)$
`hanoi(n)`	$M(n) = 2M(n-1) + 1$ , $M(0)=0$ moves	$2^n - 1$ moves	$\Theta(n)$
`gcd(a, b)` (Euclid)	one call per remainder step	$O(\lg\min(a,b))$ for positive $a,b$	same

Here $F_k$ is the $k$ -th Fibonacci number ( $F_0 = 0$ , $F_1 = 1$ ) and $\varphi = (1+\sqrt5)/2 \approx 1.618$ .

Why $C(n) = 2F_{n+1} - 1$ . Let $D(n) = C(n) + 1$ . Then $D(n) = D(n-1) + D(n-2)$ with $D(0) = D(1) = 2$ , so $D(n) = 2F_{n+1}$ . Checks: $C(5) = 2 \cdot 8 - 1 = 15$ and $C(10) = 2 \cdot 89 - 1 = 177$ .

Why naive Fibonacci is slow. The same subproblems are recomputed: fib(5) computes fib(3) twice and fib(2) three times. Memoisation stores each result the first time it is computed, so each of fib(0) to fib(n) is evaluated once and the time becomes $\Theta(n)$ . This is the idea behind dynamic programming.

Standard functions

C

/* fib/power/hanoi/digsum: n >= 0; all arithmetic must fit its result type. */
/* gcd: positive a,b for the logarithmic bound; exclude INT_MIN % -1. */
/* Mathematical asymptotics assume unbounded inputs; C also needs sufficient stack. */
int fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }

long power(long x, int n) {                /* x^n, n >= 0 */
    if (n == 0) return 1;
    long h = power(x, n / 2);              /* one recursive call, reused */
    return n % 2 ? h * h * x : h * h;
}

void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to);           /* move n-1 out of the way */
    /* move disk n from 'from' to 'to' */
    hanoi(n - 1, via, to, from);           /* move n-1 on top of it */
}

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int digsum(int n) { return n < 10 ? n : n % 10 + digsum(n / 10); }   /* n >= 0 */

Writing power(x, n/2) * power(x, n/2) instead of saving h makes two calls per level, and the call count becomes $\Theta(n)$ instead of $\Theta(\lg n)$ .

Worked examples

All outputs below are for C11 with gcc on x86-64 Linux (LP64).

Example 1. fact(5) is 120 and fact_acc(10, 1) is 3628800.

Example 2. fib(5) returns 5 and makes 15 calls; fib(10) returns 55 and makes 177 calls.

Example 3. power(3, 13) is 1594323, with 5 calls: $n = 13, 6, 3, 1, 0$ . power(2, 10) is 1024.

Example 4. hanoi(4, ...) makes $2^4 - 1 = 15$ moves.

Example 5. gcd(84, 36): $\gcd(84,36) \to \gcd(36,12) \to \gcd(12,0) = 12$ . digsum(9475) is $5 + 7 + 4 + 9 = 25$ .

Example 6 (an evaluation-order trap). In printf("%d %d\n", sum(100), maxdepth); where sum updates the global maxdepth, the order in which the two arguments are evaluated is unspecified. With gcc on x86-64 the arguments are evaluated right to left, so maxdepth is read first and 0 is printed. Call sum in a separate statement first. See Operators and Expressions.

Important properties and observations

Correctness argument = induction: prove the base cases, then assume the calls on smaller arguments are correct and show the current call is.
Recursion can be rewritten iteratively with an explicit stack. An equivalent tail-recursion-eliminated iterative form uses $O(1)$ auxiliary call-stack space if local storage is constant; the recursive C source itself has no guaranteed tail-call optimization.
With constant-sized frames and no other live auxiliary allocations, stack space is $\Theta(\text{depth})$ . In general sum storage over live calls and work over all calls; multiply call count by a per-call cost only when that cost is uniform or an explicit bound.
Each activation has its own automatic variables, but a static local or a global is shared by all activations. A recursive function with a static counter behaves very differently from one with an automatic counter; see Scope, Storage Classes and Linkage.
Recursion trees with repeated subtrees signal that memoisation or dynamic programming would help.

GATE examination perspective

Output of a recursive function with printf before and after the call: separate winding output from unwinding output.
Return value questions: evaluate bottom-up from the base case, writing a small table of $f(0), f(1), \ldots$ .
Number of calls or additions: draw the recursion tree or write the recurrence; for Fibonacci-like code use $2F_{n+1} - 1$ calls.
static variables inside recursive functions: one copy shared across calls.
Tower of Hanoi: $2^n - 1$ moves.
Complexity: set up $T(n)$ and solve (see the algorithms notes on recurrences).

Summary

Functions and Parameter Passing: prerequisite.
Recursion Tracing and Call Counting: dependent.
Stacks: related. The call stack and recursion elimination.
Binary Tree Traversals: dependent. Recursive traversal.
Scope, Storage Classes and Linkage: related. static locals in recursion.
Operators and Expressions: related. Unspecified order of argument evaluation.

Recursion

Introduction

Prerequisites

Core concepts

Base case and recursive case

How a recursive call executes

Forms of recursion

Tail recursion and accumulators

Order of work: before or after the call

How it works: costs of standard recursions

Standard functions

Worked examples

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Base case and recursive case

How a recursive call executes

Forms of recursion

Tail recursion and accumulators

Order of work: before or after the call

How it works: costs of standard recursions

Standard functions

Worked examples

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps