Basic Recursion in C: Call Stack, Worked Traces and Exam Patterns

Recursion looks like a function simply repeating itself, but most mistakes come from losing track of the base case, pending work and return order. Recursion questions become manageable when you trace C calls, compute exact outputs and costs, and apply a repeatable solving method.

Related reading: Recursion MCQs and Recursion and stacks.

Basic recursion in C programming: base case, recursive case and progress

Direct recursion means a function calls itself with a smaller input. A correct recursive function has three obligations: a base case that returns without another call, a recursive case that reduces the problem, and guaranteed progress towards the base case. In indirect recursion, functions call one another in a cycle, but the same obligations still matter.

Consider this warm-up:

void countdown(int n) {
    if (n == 0) return;
    printf("%d ", n);
    countdown(n - 1);
}

For countdown(3), the calls are countdown(3), countdown(2), countdown(1) and countdown(0). The output is 3 2 1. The base-case invocation countdown(0) still exists, even though it prints nothing.

The Coding & DSA category is the broader route for C programming and data-structure study.

Factorial recursion in C: work fact(5) from calls to returns

For non-negative integers, use:

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

Its contract is: fact(n) returns n! for n >= 0. Negative input is outside its valid domain.

The descent is:

fact(5)
-> 5 * fact(4)
-> 5 * 4 * fact(3)
-> 5 * 4 * 3 * fact(2)
-> 5 * 4 * 3 * 2 * fact(1)

Now unwind in reverse: fact(1)=1, fact(2)=2*1=2, fact(3)=3*2=6, fact(4)=4*6=24, and fact(5)=5*24=120.

There are five invocations and five simultaneously active frames at maximum depth. Each frame lives on the call stack, the LIFO structure explained in Stacks and Queues: Operations and Uses, and stores its own n and pending multiplication.

Recursive output tracing: solve trace(5) without guessing

This function performs work both before and after its recursive call:

void trace(int n) {
    if (n <= 0) return;
    printf("%d ", n);
    trace(n - 2);
    printf("%d ", n);
}

The calls are trace(5), trace(3), trace(1) and trace(-1). Descent prints 5 3 1. The base case returns, then unwinding prints 1 3 5. The exact output is 5 3 1 1 3 5.

For such questions, draw one row per invocation. Record pre-call output on the left, then read post-call output from the bottom row upwards. Here there are four total invocations, including the base-case call, and four frames at maximum depth.

Recursive time and space: compare fact(5) with naive fib(5)

Factorial follows T(n)=T(n-1)+constant, so its time is Theta(n) and its auxiliary stack space is Theta(n). For the worked input, fact(5) makes five calls and returns 120.

Naive Fibonacci branches:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

The values are fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3 and fib(5)=5. To count calls, use C(0)=C(1)=1 and C(n)=1+C(n-1)+C(n-2). Therefore C(2)=3, C(3)=5, C(4)=9 and C(5)=15.

Branching repeats subproblems. Naive Fibonacci time is Theta(phi^n), commonly upper-bounded by O(2^n), while its maximum stack depth remains Theta(n). The link between a recurrence and its growth rate is developed in Time Complexity and Asymptotic Notation. Memoisation removes the repeated evaluation of overlapping subproblems.

Recursion versus iteration: choose from the problem shape

An iterative factorial starts with result=1. It reaches 2 after i=2, 6 after i=3, 24 after i=4, and 120 after i=5. It matches fact(5)=120 without five call frames.

Recursion is natural for recursively defined structures, but it is not automatically faster. A binary-tree traversal can process the root, recursively traverse the left subtree, then recursively traverse the right subtree because the data itself has recursive shape.

Basic recursion mistakes: why they fail and how to repair them

• Wrong base condition: If the trace(5) guard becomes n == 0, arguments follow 5, 3, 1, -1, -3, ... and never reach zero. Calls continue until stack exhaustion. Use n <= 0 for this decrement-by-two function.

• No progress or wrong progress: Calling fact(n) repeats the same state, while fact(n + 1) moves away from the base. Write the decreasing measure beside the call, here n - 1, and prove it reaches n <= 1.

• Return-order or domain mistake: A statement after the recursive call runs during unwinding, not descent. Split every frame into pre-call and post-call work. Also reject negative factorial input at the public boundary because it violates the function contract.

Basic recursion exam patterns: trace, count, evaluate and analyse

Recurring tasks ask you to predict printed output, compute a returned value, count calls or maximum depth, and derive time plus auxiliary space. For these functions, trace(5) prints 5 3 1 1 3 5, fact(5) returns 120 with five calls, and fib(5) returns 5 with 15 calls.

Changing only the base case can change the count, so never import an answer from a similar-looking function. Use this checklist:

1. Copy the base case exactly.

2. List argument values on descent.

3. Evaluate deferred operations on unwind.

4. Count every invocation, including the base-case invocation.

GATE Guidance by Sanchit Sir provides a broader subject-wise preparation route when you want to place recursion inside a complete CS sequence.

Basic recursion: the short version and next step

• Identify the base case.

• Prove progress towards it.

• State the smaller call's contract before trusting its result.

• Unwind pending work in reverse order.

• Analyse running time separately from stack space.

Keep the three anchor answers clear: fact(5)=120, trace(5) prints 5 3 1 1 3 5, and naive fib(5) makes 15 calls.

For the wider sequence with concepts, MCQs and coding practice, continue with the C Language course.