Recursion in C – A Complete Guide with Examples

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive solution has two parts: a base case that stops the recursion, and a recursive case that breaks the problem down. When the structure of a problem is naturally self-similar — trees, nested structures, divide-and-conquer algorithms — recursion produces cleaner code than the equivalent loop. This guide builds from the simplest examples up to real algorithms, with a working program at every step.

How Recursion Works — The Call Stack

Each function call gets its own stack frame with its own local variables. Recursive calls stack up until the base case is reached, then each frame returns in reverse order:

#include <stdio.h>

void countdown(int n)
{
    if (n <= 0) {          /* base case */
        printf("Go!\n");
        return;
    }
    printf("%d...\n", n);
    countdown(n - 1);      /* recursive case */
}

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

3...
2...
1...
Go!

Each call to countdown pushes a new frame onto the stack. When n reaches 0, the base case fires, and every frame returns — unwinding the stack.

Factorial

The textbook example: n! = n × (n-1)!, with 0! = 1 as the base case.

#include <stdio.h>

long factorial(int n)
{
    if (n <= 1)
        return 1;           /* base case */
    return n * factorial(n - 1);
}

int main(void)
{
    int i;
    for (i = 0; i <= 10; i++)
        printf("%2d! = %ld\n", i, factorial(i));
    return 0;
}

 0! = 1
 1! = 1
 2! = 2
 3! = 6
 4! = 24
 5! = 120
 6! = 720
 7! = 5040
 8! = 40320
 9! = 362880
10! = 3628800

Fibonacci

fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1:

#include <stdio.h>

int fib(int n)
{
    if (n <= 0) return 0;
    if (n == 1)  return 1;
    return fib(n - 1) + fib(n - 2);
}

int main(void)
{
    int i;
    for (i = 0; i <= 10; i++)
        printf("fib(%2d) = %d\n", i, fib(i));
    return 0;
}

fib( 0) = 0
fib( 1) = 1
fib( 2) = 1
fib( 3) = 2
fib( 4) = 3
fib( 5) = 5
fib( 6) = 8
fib( 7) = 13
fib( 8) = 21
fib( 9) = 34
fib(10) = 55

The naive recursive Fibonacci calls fib(n-2) and fib(n-1) separately, recomputing the same values repeatedly. Its time complexity is O(2ⁿ) — unusable for large n. The iterative version is O(n); see Fibonacci using Recursion for a comparison.

GCD — Euclid’s Algorithm

Euclid’s algorithm is an elegant recursive solution: gcd(a, b) = gcd(b, a % b), stopping when b is 0:

#include <stdio.h>

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

int main(void)
{
    printf("gcd(48, 18) = %d\n", gcd(48, 18));
    printf("gcd(100, 75) = %d\n", gcd(100, 75));
    return 0;
}

gcd(48, 18) = 6
gcd(100, 75) = 25

Binary Search — Recursive

Binary search divides the sorted array in half with each call:

#include <stdio.h>

int binary_search(int arr[], int low, int high, int target)
{
    int mid;

    if (low > high)
        return -1;                      /* base case: not found */

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

    if (arr[mid] == target)
        return mid;                     /* base case: found */
    else if (arr[mid] < target)
        return binary_search(arr, mid + 1, high, target);
    else
        return binary_search(arr, low,  mid - 1, target);
}

int main(void)
{
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = 10;
    int idx;

    idx = binary_search(arr, 0, n - 1, 23);
    if (idx != -1)
        printf("Found 23 at index %d\n", idx);
    else
        printf("Not found\n");

    idx = binary_search(arr, 0, n - 1, 50);
    printf("50: %s\n", idx != -1 ? "found" : "not found");
    return 0;
}

Found 23 at index 5
50: not found

Power Function — Divide and Conquer

Computing xⁿ efficiently: if n is even, x^n = (x^(n/2))^2. This halves the number of multiplications:

#include <stdio.h>

long power(long base, int exp)
{
    long half;

    if (exp == 0) return 1;
    if (exp == 1) return base;

    half = power(base, exp / 2);

    if (exp % 2 == 0)
        return half * half;
    else
        return base * half * half;
}

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

2^10  = 1024
3^5   = 243
5^0   = 1

The naive loop takes O(n) multiplications. This recursive divide-and-conquer takes O(log n) — the same idea behind fast modular exponentiation used in cryptography.

Towers of Hanoi

The classic recursion puzzle: move n disks from peg A to peg C using peg B, never placing a larger disk on a smaller one. The recursive insight: move n-1 disks out of the way, move the largest disk, then move n-1 disks back.

#include <stdio.h>

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

int main(void)
{
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

3 disks require 7 moves. n disks require 2ⁿ − 1 moves — this is provably optimal. See the full program with peg state display at Towers of Hanoi in C.

Recursion vs Iteration

Aspect	Recursion	Iteration
Code clarity	Natural for self-similar problems (trees, divide-and-conquer)	Natural for sequential processing
Stack usage	One frame per call — deep recursion can stack-overflow	Constant stack (no frame per iteration)
Performance	Function-call overhead; redundant computation without memoization	Generally faster for simple loops
Best for	Tree traversals, divide-and-conquer, backtracking, grammar parsing	Factorial, Fibonacci (when n is large), file processing

Common Recursion Mistakes

Mistake	What happens	Fix
Missing base case	Infinite recursion → stack overflow (segfault)	Every recursive function must have at least one reachable base case
Base case never reached	Infinite recursion — recursive step doesn’t approach the base case	Ensure each recursive call moves closer to the base case
Redundant recomputation	Exponential time (e.g., naive Fibonacci)	Use iteration or memoization (store computed results)
Stack overflow on deep input	Program crashes for large n	Convert tail-recursive functions to iteration; limit input depth

How to Compile

gcc -ansi -Wall -Wextra -o recursion recursion.c

Related C Programs

📖 Chapters 4 and 5 of The C Programming Language by K&R (Amazon.in) · Amazon.com cover recursive functions and the pointer-based patterns that make tree and graph recursion work in C.

Preparing for a C interview? Practice with the C Programming Quiz — 150+ questions, free on Android.