C Recursion

Recursion is a technique where a function solves a problem by calling itself with a smaller version of the same problem. It matters because many tasks, such as walking tree structures, searching sorted data, parsing nested input, and computing mathematical definitions, are naturally recursive. In C, recursion is powerful, but it must be written carefully because every recursive call uses stack memory.

Overview: How Recursion Works

A recursive function has two essential parts: a base case that stops the recursion, and a recursive case that calls the same function again with input that is closer to the base case. Without both parts, the program either never stops or stops without solving the full problem.

When a C function is called, the program creates a new function call record, often called a stack frame. That frame stores information such as parameters, local variables, and the return address. A recursive call creates another independent frame for the same function. The old frame is paused until the deeper call returns. This means a recursive function does not overwrite its previous parameters; each call has its own copy of automatic local variables.

For example, factorial(5) calls factorial(4), which calls factorial(3), and so on until the base case factorial(1). Then the returns unwind: 1 returns to the caller, then 2 * 1, then 3 * 2, and eventually 5 * 24. This two-phase behavior is common: first the calls go deeper, then results come back up.

Recursion is not automatically better than loops. A loop is usually simpler and uses constant stack space for straightforward repetition. Recursion is most useful when the problem is self-similar: a directory contains directories, an expression contains subexpressions, a tree node contains child nodes, or a sorted range can be split into smaller ranges.

Syntax

return_type function_name(parameters) {
    if (base_condition) {
        return base_value;
    }

    return expression_using(function_name(smaller_problem));
}

Part	Purpose
return_type	The type returned by every path through the function, such as int or long long.
base_condition	The condition that says the problem is small enough to answer directly.
base_value	The direct answer for the base case.
smaller_problem	Arguments that move the function closer to the base case.
expression_using(...)	How the current call combines its work with the recursive result.

Examples

Example 1: Factorial

#include <stdio.h>

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

    return n * factorial(n - 1);
}

int main(void) {
    printf("0! = %lld\n", factorial(0));
    printf("1! = %lld\n", factorial(1));
    printf("5! = %lld\n", factorial(5));
    printf("10! = %lld\n", factorial(10));
    return 0;
}

Output:

0! = 1
1! = 1
5! = 120
10! = 3628800

This program matches the mathematical definition of factorial: 0! and 1! are 1, and every larger value is n * (n - 1)!. The return type is long long because factorials grow quickly, but even long long overflows for fairly small inputs.

Example 2: Recursively Sum an Array

#include <stdio.h>

int sum_array(const int values[], int count) {
    if (count == 0) {
        return 0;
    }

    return values[0] + sum_array(values + 1, count - 1);
}

int main(void) {
    int scores[] = {4, 7, -2, 9, 5};
    int count = (int)(sizeof(scores) / sizeof(scores[0]));

    printf("sum = %d\n", sum_array(scores, count));
    return 0;
}

Output:

sum = 23

Here the smaller problem is the rest of the array. The expression values + 1 points to the next element, and count - 1 says there is one fewer value left to process. The base case is an empty range, whose sum is 0. The const keyword communicates that the function reads the array but does not modify it.

Example 3: Recursive Binary Search

#include <stdio.h>

int binary_search_recursive(const int values[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }

    int middle = left + (right - left) / 2;

    if (values[middle] == target) {
        return middle;
    }
    if (target < values[middle]) {
        return binary_search_recursive(values, left, middle - 1, target);
    }

    return binary_search_recursive(values, middle + 1, right, target);
}

void print_result(const int values[], int count, int target) {
    int index = binary_search_recursive(values, 0, count - 1, target);

    if (index == -1) {
        printf("%d was not found\n", target);
    } else {
        printf("%d found at index %d\n", target, index);
    }
}

int main(void) {
    int values[] = {2, 3, 5, 8, 13, 21, 34};
    int count = (int)(sizeof(values) / sizeof(values[0]));

    print_result(values, count, 3);
    print_result(values, count, 13);
    print_result(values, count, 22);
    return 0;
}

Output:

3 found at index 1
13 found at index 4
22 was not found

Binary search is a strong recursive example because each call discards half of the remaining range. The base case left > right means there is no range left to search. The middle calculation uses left + (right - left) / 2, which avoids overflow that could happen with (left + right) / 2 when indexes are very large.

How It Works Step by Step

Consider factorial(4). The first call cannot answer directly, so it waits for factorial(3). That call waits for factorial(2), which waits for factorial(1). The base case returns 1. Then factorial(2) returns 2 * 1, factorial(3) returns 3 * 2, and factorial(4) returns 4 * 6.

During this process, four stack frames exist at the deepest point. If the recursion goes too deep, the stack can run out of space and the program may crash. C does not guarantee automatic detection of this problem, and it does not require compilers to optimize tail recursion. If you need millions of steps, use a loop unless you have measured and controlled the stack usage.

Common Mistakes

Missing or Unreachable Base Case

A recursive function must have a base case that can actually be reached. A countdown that calls countdown(n) again with the same n never makes progress. The fixed version decreases n before the next call.

#include <stdio.h>

void countdown(int n) {
    if (n < 0) {
        return;
    }

    printf("%d\n", n);
    countdown(n - 1);
}

int main(void) {
    countdown(3);
    return 0;
}

Output:

3
2
1
0

Doing Work After a Return

Code after return in the same block is unreachable. If the recursive result must be printed, saved, or combined with another value, do that before returning or return the combined expression directly. For example, use return values[0] + sum_array(values + 1, count - 1);, not a separate calculation after an earlier return.

Forgetting Input Limits

Recursive mathematical examples can overflow even when the recursion itself is correct. factorial(25) is too large for a signed 64-bit integer. Real programs should validate input, choose a wider numeric representation, or report that the requested value is outside the supported range.

Best Practices

• Write the base case first, and make it handle the smallest valid input clearly.
• Make sure every recursive call moves closer to the base case.
• Keep parameters explicit. Pass indexes, counts, or pointers that describe the current subproblem.
• Prefer recursion for naturally nested or divide-and-conquer problems, not ordinary counting loops.
• Watch stack depth. Deep recursion can fail even if the algorithm is logically correct.
• Use types large enough for the result, and still check whether overflow is possible.
• Test base cases, one-step recursive cases, typical cases, and boundary values.
• Keep recursive functions small. Complicated state changes are harder to reason about across many stack frames.

Practice Exercises

1. Write a recursive function int power(int base, int exponent) for non-negative exponents. Test power(2, 0), power(2, 5), and power(3, 4).
2. Write a recursive function that prints a string backward. Hint: print the rest of the string first, then print the current character.
3. Write a recursive function that finds the largest value in an integer array. Use the last element as one candidate and recursively find the largest value in the earlier elements.

Summary

• Recursion means a function calls itself to solve a smaller version of the same problem.
• Every recursive function needs a reachable base case and a recursive case that makes progress.
• Each recursive call gets its own stack frame with its own parameters and local variables.
• Recursive calls unwind in reverse order after the base case returns.
• Recursion is elegant for nested, tree-like, and divide-and-conquer problems, but loops are often better for simple repetition.
• In C, stack depth and numeric overflow are practical concerns, so recursive code should be tested with boundary inputs.