C Recursion: Recursive Functions, Base Case & Stack Guide 2026

What Is Recursion

Recursion occurs when a function calls itself. It’s a powerful technique for solving problems that can be broken into smaller, identical sub-problems. Instead of using loops to repeat work, a recursive function delegates the smaller version of the problem to another call of itself.

You need two things for successful recursion: a base case (when to stop) and a recursive case (how to break the problem down). Without a base case, the function calls itself infinitely until the program crashes.

Building on what you learned about functions and scope, each recursive call creates its own set of local variables on the stack. This is what makes recursion work — each call operates independently.

Anatomy of a Recursive Function

Every recursive function has the same structure:

return_type recursive_function(parameters) {
    // 1. BASE CASE — stop condition
    if (base_condition) {
        return base_value;
    }

    // 2. RECURSIVE CASE — call yourself with a smaller problem
    return recursive_function(smaller_parameters);
}

The simplest example — factorial:

// 5! = 5 × 4 × 3 × 2 × 1 = 120
int factorial(int n) {
    // Base case: 0! = 1 and 1! = 1
    if (n <= 1) return 1;

    // Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1);
}

How factorial(5) executes:

factorial(5)
→ 5 * factorial(4)
→ 5 * 4 * factorial(3)
→ 5 * 4 * 3 * factorial(2)
→ 5 * 4 * 3 * 2 * factorial(1)
→ 5 * 4 * 3 * 2 * 1      // Base case reached
→ 120                      // Results propagate back up

How the Call Stack Works

Each function call pushes a stack frame onto the call stack. The frame holds the function’s local variables, parameters, and return address. With recursion, multiple frames for the same function stack up:

// Call stack during factorial(4):

| factorial(1) | n=1, returns 1      | ← Top (most recent)
| factorial(2) | n=2, waiting         |
| factorial(3) | n=3, waiting         |
| factorial(4) | n=4, waiting         |
| main()       |                      | ← Bottom

When factorial(1) returns, its frame is popped. Then factorial(2) computes 2 * 1 = 2 and returns, and so on, unwinding back to the original call.

This is why the stack can overflow with too many recursive calls — each call consumes stack memory. A factorial(100000) call would need 100,000 stack frames.

Classic Recursion Examples

Fibonacci sequence:

// 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
int fibonacci(int n) {
    if (n <= 0) return 0;  // Base case 1
    if (n == 1) return 1;   // Base case 2
    return fibonacci(n - 1) + fibonacci(n - 2);  // Two recursive calls
}

Warning: This naive implementation is extremely slow for large n because it recalculates the same values repeatedly. fibonacci(40) makes over a billion function calls. Use iteration or memoization for practical Fibonacci computation.

Sum of digits:

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}
// digit_sum(1234) → 4 + digit_sum(123) → 4+3+digit_sum(12) → 4+3+2+1 = 10

Power function:

double power(double base, int exp) {
    if (exp == 0) return 1.0;
    if (exp < 0) return 1.0 / power(base, -exp);
    return base * power(base, exp - 1);
}

String reversal:

void reverse_print(const char str[], int index) {
    if (str[index] == '\0') return;  // Base case
    reverse_print(str, index + 1);    // Recurse first
    printf("%c", str[index]);          // Print on the way back
}
// reverse_print("hello", 0) prints "olleh"

Recursion vs Iteration

Every recursive solution can be rewritten as an iterative one using loops. Here’s factorial both ways:

// Recursive
int factorial_recursive(int n) {
    if (n <= 1) return 1;
    return n * factorial_recursive(n - 1);
}

// Iterative
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Iteration is generally faster (no function call overhead) and uses constant memory. Recursion is clearer for problems that are naturally recursive — tree traversal, divide-and-conquer algorithms, and parsing nested structures.

Tail Recursion

A function is tail recursive when the recursive call is the last operation — nothing happens after it returns. Some compilers can optimize tail recursion into a loop, eliminating the stack overhead:

// NOT tail recursive — multiplication happens after recursive call
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // Must multiply after call returns
}

// Tail recursive — accumulator carries the result
int factorial_tail(int n, int accumulator) {
    if (n <= 1) return accumulator;
    return factorial_tail(n - 1, n * accumulator);  // Nothing after this
}

// Wrapper for clean API
int factorial_optimized(int n) {
    return factorial_tail(n, 1);
}

GCC can optimize tail calls with -O2 or higher optimization levels. However, the C standard doesn’t guarantee tail call optimization, so don’t rely on it for correctness.

Common Recursive Patterns

Binary search:

int binary_search(const int arr[], int low, int high, int target) {
    if (low > high) return -1;  // Not found

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) return mid;
    if (arr[mid] > target)
        return binary_search(arr, low, mid - 1, target);
    return binary_search(arr, mid + 1, high, target);
}

GCD (Euclidean algorithm):

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
// gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6

Tower of Hanoi:

void hanoi(int n, char from, char to, char aux) {
    if (n == 0) return;
    hanoi(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

Stack Overflow

Every recursive call uses stack memory. If recursion goes too deep, you get a stack overflow — the program crashes. The default stack size varies by platform (typically 1-8 MB), which limits recursion depth to roughly 10,000-100,000 calls depending on frame size.

// This WILL crash — infinite recursion
void infinite(void) {
    infinite();  // No base case!
}

// This might crash for large n — too deep
int deep_recursion(int n) {
    if (n == 0) return 0;
    return 1 + deep_recursion(n - 1);
}
// deep_recursion(1000000) — likely stack overflow

To avoid stack overflow: ensure your base case is reachable, ensure each recursive call makes progress toward the base case, and consider iteration for problems with potentially large depth.

When to Use Recursion

Use recursion when: The problem is naturally recursive (trees, fractals, divide-and-conquer), the code is dramatically simpler than iteration, or the recursion depth is bounded and small.

Use iteration when: Performance matters, the problem is naturally sequential (processing a list), or recursion depth could be very large.

Use memoization when: Recursive subproblems overlap (like Fibonacci), converting exponential time complexity to linear.

Practical Examples

A complete program demonstrating multiple recursive techniques:

#include <stdio.h>

// Prototypes
int factorial(int n);
int fibonacci_memo(int n, int memo[]);
int gcd(int a, int b);
void print_binary(int n);

int main(void) {
    // Factorial
    printf("10! = %d\n", factorial(10));

    // Fibonacci with memoization
    int memo[50] = {0};
    printf("Fib(20) = %d\n", fibonacci_memo(20, memo));

    // GCD
    printf("GCD(48, 18) = %d\n", gcd(48, 18));

    // Binary representation
    printf("42 in binary: ");
    print_binary(42);
    printf("\n");

    return 0;
}

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

int fibonacci_memo(int n, int memo[]) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n];  // Already computed
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
    return memo[n];
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

void print_binary(int n) {
    if (n == 0) return;
    print_binary(n / 2);
    printf("%d", n % 2);
}

Recursion completes your understanding of how functions can call each other — and themselves. Combined with scope and the stack, you now have a solid foundation. Next: header files, which let you organize functions across multiple files.