C Recursion Factorial, Fibonacci, Tower of Hanoi

Call Stack Trace

Each recursive call gets its own stack frame with its own parameters and local variables. When a base case returns, calls unwind in reverse order. Tracing that stack is the fastest way to understand recursion.

Write down n for each call.
Mark the base case.
Resolve return values from the bottom upward.

Recursion with Memoization

Some recursive functions repeat the same subproblems. Fibonacci is the classic example. Memoization stores answers so the function does not recompute the same value again and again.

Use memoization for overlapping subproblems.
Initialize memo storage clearly.
Check array bounds before using memo indexes.

Backtracking Mindset

Backtracking uses recursion to choose, explore, and undo. It appears in combinations, permutations, maze solving, and constraint problems. The undo step keeps the next branch clean.

Choose one option.
Recurse into the smaller state.
Undo the choice before trying the next option.

Trace Frames and Prove Progress

A recursive C function needs two proofs: a base case handles the smallest valid input, and every recursive branch moves strictly toward it. Trace a call by writing each argument and pending operation as a stack frame. If the same argument can reappear before a result returns, termination is not established.

Depth is also a resource boundary. Tail position does not guarantee optimization in portable C, so an input-sized call chain can exhaust the process stack. Use iteration or an explicit stack when the supported input can create deep or cyclic traversal.

Test the base case directly before a typical recursive case.
Reject inputs outside the recurrence domain before the first recursive call.
For trees or graphs, distinguish structural depth from total node count.

Traceable Factorial

#include <stdio.h>

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

int main() {
    printf("%d\n", factorial(5));
}

Recursive Array Sum

#include <stdio.h>

int sum(int values[], int n) {
    if (n == 0) {
        return 0;
    }
    return values[n - 1] + sum(values, n - 1);
}

int main() {
    int values[] = {4, 7, 2};
    printf("%d\n", sum(values, 3));
}

Memoized Fibonacci

#include <stdio.h>

int fib(int n, int memo[]) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

int main() {
    int memo[10];
    for (int i = 0; i < 10; i++) memo[i] = -1;
    printf("%d\n", fib(8, memo));
}

Recursive Countdown Trace

#include <stdio.h>

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

int main() {
    countdown(3);
}

Before you move on