C · Advanced

Recursion in C

In short: A recursive function solves a problem by calling itself on a smaller version of the same problem, stopping at a base case it can answer directly. Each call gets its own stack frame with its own parameters and locals, so calls unwind in reverse order; without a reachable base case the stack overflows and the program crashes.

A function defined in terms of itself

Some problems are most naturally described in terms of themselves. The digit sum of 4721 is 1 plus the digit sum of 472; the sum of an array is its first element plus the sum of the rest; sorting a list is sorting each half and merging. A recursive function writes that description directly: it handles the smallest case outright and otherwise does a little work and calls itself on a smaller input.

Every recursive function has two parts. The base case is an input small enough to answer without recursion, such as an exponent of zero or an empty array; it must exist and must be reached, or the calls never stop. The recursive case reduces the input, by one element, one digit or half the range, calls the function on the reduced input, and combines the result with its own contribution.

C implements calls with a stack. Each call pushes a frame holding the function's parameters, local variables and the address to return to; when the function returns, the frame is popped. A recursive call is not special: trace(3) calls trace(2), which calls trace(1), and each of those calls has its own n. Work placed before the recursive call happens on the way down, and work placed after it happens on the way back up, in reverse order.

The stack has a limited size, typically a few megabytes set by the operating system. A depth in the thousands is usually fine, a depth in the millions is not, and a large local array in a recursive function shrinks the limit fast; when the depth is proportional to the input size, a loop is the safer choice for big inputs. Some compilers turn a call in tail position into a jump at higher optimisation levels, but the C standard does not promise it, so never rely on it for correctness.

Recursion earns its place when the problem divides into independent pieces of the same shape: merge sort splits the array in half and recurses on each half, so the depth is only log2(n); binary search does the same with one half; walking a directory tree or a linked structure visits each child with the same function. In those cases a loop would need an explicit stack of its own, and the recursive version is shorter and clearer. Recursion is wasteful when the same sub-problems recur; a loop or a table of stored results is then far faster.

Syntax

return_type name(parameters) {
    if (base case) {
        return direct answer;
    }
    /* work on the way down (optional) */
    result = name(smaller input);        /* the recursive call */
    /* work on the way back up (optional) */
    return combine(result, own part);
}

long power(int base, int exponent) {
    if (exponent == 0) return 1;                     /* base case */
    return base * power(base, exponent - 1);         /* recursive case */
}

A function may call itself in its own body without a separate prototype, because its name is already declared by the time the body is compiled.

Recursion or a loop?

Watching the stack grow and unwind

A function that prints on the way in and on the way out, and a recursive power.

#include <stdio.h>

void trace(int n) {
    printf("enter %d\n", n);
    if (n == 0) {
        printf("base case reached\n");
    } else {
        trace(n - 1);
    }
    printf("leave %d\n", n);
}

long power(int base, int exponent) {
    if (exponent == 0) {
        return 1;
    }
    return base * power(base, exponent - 1);
}

int main(void) {
    trace(3);
    printf("3^4 = %ld\n", power(3, 4));
    printf("2^10 = %ld\n", power(2, 10));
    return 0;
}

enter 3
enter 2
enter 1
enter 0
base case reached
leave 0
leave 1
leave 2
leave 3
3^4 = 81
2^10 = 1024

trace(3) prints enter 3 and then calls trace(2) before printing anything else, so the enter lines appear in descending order. Only when trace(0) hits the base case does anything return; the leave lines then print in ascending order, because each call resumes after its recursive call and finishes its own printf. At the deepest point four frames of trace exist at once, each with its own n. power follows the same pattern with a result: power(3, 4) is 3 * power(3, 3), and so on down to power(3, 0), which returns 1 and lets the multiplications happen on the way up.

Recursion on digits and on arrays

Printing a number in binary, most significant digit first, and summing and maxing an array through a pointer.

#include <stdio.h>

void print_binary(unsigned int n) {
    if (n > 1) {
        print_binary(n / 2);     /* print the higher digits first */
    }
    putchar('0' + n % 2);
}

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

int max_array(const int *values, int count) {
    if (count == 1) {
        return values[0];
    }
    int rest = max_array(values + 1, count - 1);
    return values[0] > rest ? values[0] : rest;
}

int main(void) {
    unsigned int codes[3] = {5, 18, 255};
    for (int i = 0; i < 3; i++) {
        printf("%u in binary is ", codes[i]);
        print_binary(codes[i]);
        printf("\n");
    }

    int loads[5] = {14, 7, 22, 9, 16};
    printf("sum: %d\n", sum_array(loads, 5));
    printf("max: %d\n", max_array(loads, 5));
    return 0;
}

5 in binary is 101
18 in binary is 10010
255 in binary is 11111111
sum: 68
max: 22

Arithmetic yields the lowest binary digit first, n % 2, but it must be printed last, so print_binary recurses on n / 2 before printing; the base case is a value below 2, a single digit. sum_array and max_array express the array as its first element and the rest, moving the pointer forward and the count down, which uses the pointer arithmetic from the pointers lesson. sum_array can stop at an empty array with a sum of 0; max_array cannot, because an empty array has no maximum, so its base case is a single element.

Divide and conquer: merge sort

The array is split in half until the pieces are trivially sorted, then merged back together; each split is printed with its depth.

#include <stdio.h>

void merge(int a[], int tmp[], int lo, int mid, int hi) {
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }
    while (i < mid) {
        tmp[k++] = a[i++];
    }
    while (j < hi) {
        tmp[k++] = a[j++];
    }
    for (k = lo; k < hi; k++) {
        a[k] = tmp[k];
    }
}

void merge_sort(int a[], int tmp[], int lo, int hi, int depth) {
    if (hi - lo < 2) {
        return;               /* base case: 0 or 1 element is already sorted */
    }
    int mid = lo + (hi - lo) / 2;
    printf("%*ssplit [%d,%d) into [%d,%d) and [%d,%d)\n", depth * 2, "", lo, hi, lo, mid, mid, hi);
    merge_sort(a, tmp, lo, mid, depth + 1);
    merge_sort(a, tmp, mid, hi, depth + 1);
    merge(a, tmp, lo, mid, hi);
}

int main(void) {
    int scores[6] = {52, 17, 88, 33, 41, 9};
    int tmp[6];
    merge_sort(scores, tmp, 0, 6, 0);
    for (int i = 0; i < 6; i++) {
        printf("%d%c", scores[i], i < 5 ? ' ' : '\n');
    }
    return 0;
}

split [0,6) into [0,3) and [3,6)
  split [0,3) into [0,1) and [1,3)
    split [1,3) into [1,2) and [2,3)
  split [3,6) into [3,4) and [4,6)
    split [4,6) into [4,5) and [5,6)
9 17 33 41 52 88

merge_sort works on the half-open range [lo, hi). A range of fewer than two elements is sorted already, so it returns at once; otherwise the range is split at the middle, both halves are sorted by recursive calls, and merge interleaves the two sorted halves into tmp before copying them back. The printed trace shows a recursion depth of only 3 for six elements; it would be about 20 for a million, because each level halves the range. That logarithmic depth is why recursion is the natural way to write this algorithm, whereas the insertion sort in the sorting lesson is a plain loop. The tmp buffer is declared once in main and shared by every call, avoiding an allocation per level.

Common mistakes

• No base case, or one that is never reached

  Why it goes wrong: power(2, -1) calls power(2, -2) and so on: the exponent never reaches 0, each call adds a frame, and the program dies with a stack overflow, reported on Linux as a segmentation fault.

  Fix: Make the base case a condition the input is guaranteed to reach, and validate arguments the function cannot handle.

   C · fixCopy

  long power(int base, int exponent) {
      if (exponent <= 0) return 1;
      return base * power(base, exponent - 1);
  }

• Recursing on the same input

  Why it goes wrong: A function that calls itself with an argument that has not shrunk, such as a forgotten - 1, never approaches the base case.

  Fix: Check that every recursive call passes a strictly smaller problem: a shorter array, a smaller number, a narrower range.

• Recomputing overlapping sub-problems

  Why it goes wrong: A term defined by the two before it, computed as f(n - 1) + f(n - 2), calls f(n - 2) twice, f(n - 3) three times and so on; the number of calls roughly doubles with each increase in n.

  Fix: Compute the terms in a loop from the bottom up, or store each computed result in an array and return the stored value when it is asked for again.

• Large local arrays in a recursive function

  Why it goes wrong: Every frame carries its own copy of every local. A char buffer[4096] inside a function that recurses a thousand deep uses four megabytes of stack, which can exceed the limit.

  Fix: Allocate large buffers once outside the recursion and pass a pointer to them, as the merge sort example does with tmp.

Where you use this

Nested structures are where recursion is hard to avoid. A directory contains files and other directories, so a function that totals the size of a directory calls itself on each subdirectory; a binary tree node has a left and a right child, so counting nodes is one plus the counts of the two subtrees; an arithmetic expression such as (2 + 3) * 4 contains sub-expressions of the same form. In each case the function handles one level and delegates the rest to itself. Combined with structs and dynamic memory, this is how tree-shaped data is built and walked in C.

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

int count_nodes(const struct Node *n) {
    if (n == NULL) {
        return 0;                                    /* base case: empty subtree */
    }
    return 1 + count_nodes(n->left) + count_nodes(n->right);
}

Key points

• A recursive function needs a base case that is always reached and a recursive case that shrinks the input.
• Each call has its own frame on the stack; work after the call runs in reverse order as the calls unwind.
• Stack space is limited: depth proportional to n is risky for large n, depth log n is fine.
• Use recursion for divide-and-conquer and for nested data; use a loop for simple sequences.
• Do not rely on tail-call optimisation in C; the standard does not guarantee it.
• When sub-problems overlap, store results or switch to a bottom-up loop.

Try it yourself

Complete digit_sum recursively: a number below 10 is its own digit sum; otherwise the answer is the last digit, n % 10, plus the digit sum of n / 10. For the input 4721 the program prints digit sum of 4721 is 14.

#include <stdio.h>

int digit_sum(int n) {
    /* base case: a single digit is its own sum
       otherwise: last digit (n % 10) plus the digit sum of the rest (n / 10) */
    return 0;
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n < 0) {
        return 1;
    }
    printf("digit sum of %d is %d\n", n, digit_sum(n));
    return 0;
}

#include <stdio.h>

int digit_sum(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + digit_sum(n / 10);
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n < 0) {
        return 1;
    }
    printf("digit sum of %d is %d\n", n, digit_sum(n));
    return 0;
}

Practise this

Exercises for this lesson are in the C practice set.

Open the C playground

Related lessons

• Functions in CHow to define and call C functions: prototypes before the first call, arguments copied by value, void functions, early returns and local variables.10 minCompleted
• Pointers in CWhat a C pointer is, how & and * work, why functions take addresses to change their caller's variables, and how pointer arithmetic walks an array.10 minCompleted
• Sorting and Searching in CLinear and binary search, insertion sort by hand, and the C library's qsort and bsearch with comparison functions, applied to arrays of ints and structs.10 minCompleted
• Arrays in CHow C arrays store same-typed values by zero-based index: initialiser lists, the sizeof length idiom, passing arrays to functions and out-of-range dangers.10 minCompleted

Frequently asked questions

How this page was checked. Every program on it was run with GCC 13 (C11) at build time by the publishing checks, and the output shown is what it printed. Running C inside the browser is not available yet, so the Run button is absent rather than pretending; copy the code and run it with GCC 13 (C11) locally.