Skip to content
Tutorials Center
My learning

Topics

C Reference ยท Functions and Scope

Recursion in C

Reference for recursion in C: base cases, recursive calls, call stack depth, mutual recursion, tail calls and when a loop is the better choice.

A recursive function calls itself, directly or through other functions. Every recursive function needs a base case that returns without recursing, and each recursive call must move closer to that base case. Without both, the calls never stop and the program runs out of stack space.

C allows recursion in any function, with no special keyword. Each call gets its own set of parameters and local variables on the call stack, so the calls do not interfere with each other. Recursion fits problems that are naturally self-similar: trees, divide and conquer, backtracking.

C
unsigned long factorial(unsigned n) {
    if (n <= 1) return 1;          /* base case */
    return n * factorial(n - 1);   /* smaller problem */
}

Try it

C Factorial, Fibonacci and the call depth

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

C Recursion on data and mutual recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Syntax

Recursion has no syntax of its own. The pattern is:

C
result f(input) {
    if (/* simplest case */) {
        return /* direct answer */;
    }
    /* reduce the input */
    return combine(f(smaller_input));
}
Part Description
Base case A condition that returns without calling the function again. Every chain of calls must reach one.
Recursive case Calls the function with a smaller or simpler argument.
Frame The stack memory for one call: parameters, locals, return address. It lives until that call returns.

Errors / undefined behavior: unbounded recursion overflows the stack, which usually crashes with a segmentation fault (SIGSEGV). The C standard does not define the stack size or what happens on overflow. Typical limits are a few megabytes (8 MB on many Linux systems, 1 MB on Windows), which allows tens of thousands of small frames.

Usage notes

  • Depth, not total calls, uses the stack. fib(30) makes over a million calls but is only 30 frames deep. A linked list of a million nodes walked recursively is a million frames deep and likely crashes.
  • Naive double recursion is slow. fib(n) recomputes the same values; use a loop, memoization with an array, or dynamic programming.
  • Tail calls. When the recursive call is the last thing the function does (like gcd), an optimizing compiler such as GCC at -O2 often turns it into a jump. The C standard does not guarantee this, so never depend on it for correctness.
  • Mutual recursion needs a prior declaration of the function used first, as with is_odd above.
  • Loops are often better. If recursion is only counting, use for. Reserve recursion for structures that branch: trees, graph searches, permutations, parsing.
  • Convert to an explicit stack (your own array) when depth can be large or unbounded and the input is not trusted.
  • Integer overflow. Recursive results grow fast: factorial(21) overflows unsigned long long. Overflow of signed types is undefined.
  • Static and global state inside a recursive function is shared by all calls; use parameters for per-call state.
  • main may call itself in C (unlike C++), but this is almost never a good idea.