C Recursion — Recursive Functions Explained with Examples

In this tutorial, you will learn about C Recursion. We cover key concepts, practical examples, and best practices to help you master this topic.

C recursion is a technique where a function calls itself to solve a problem by breaking it into smaller subproblems, requiring a base case to prevent infinite recursion and stack overflow.

What You Will Learn

• How recursive functions work with the call stack
• Defining base cases and recursive cases correctly
• Comparing recursion with iterative solutions
• Understanding tail recursion and its optimization
• Common recursion patterns: factorial, Fibonacci, tree traversal
• When to use recursion and when to avoid it

Why It Matters

Recursion is fundamental to computer science and appears in tree traversal, graph algorithms, divide-and-conquer strategies, Backtracking, and Functional Programming. In systems programming, recursion is used in directory traversal, Parsing expression grammars, and quicksort implementation. Understanding recursion also deepens your understanding of the call stack, which is essential for debugging stack overflows in production C code like the file system scanner in Durga Antivirus Pro.

Real-World Use

A file system scanner needs to visit every directory and subdirectory to check files. Writing this iteratively requires managing an explicit stack or queue. A recursive approach mirrors the tree structure naturally: scanFiles(directory) processes the current directory and calls itself for each subdirectory. This same pattern appears in JSON parsing, HTML DOM traversal, and recursive make.

Learning Path

flowchart LR
  A[Scope & Linkage] --> B[Recursion\nYou are here]
  B --> C[Variable Arguments]
  style B fill:#f90,color:#fff

Anatomy of a Recursive Function

Every recursive function has two essential parts:

1. Base case: The condition under which the function stops recursing. Without it, the function calls itself forever.
2. Recursive case: The function calls itself with modified arguments, moving toward the base case.

#include <stdio.h>

// Factorial: n! = n * (n-1)!
int factorial(int n) {
    // Base case: 0! = 1
    if (n <= 1) {
        return 1;
    }
    // Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1);
}

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

Output:

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

How Recursion Uses the Stack

Each recursive call pushes a new stack frame containing the function's parameters and local variables. When the base case returns, frames pop off in reverse order (last in, first out).

#include <stdio.h>

void trace(int n) {
    printf("Entering trace(%d), stack address of n: %p\n", n, (void*)&n);
    if (n > 0) {
        trace(n - 1);
    }
    printf("Exiting trace(%d)\n", n);
}

int main() {
    trace(3);
    return 0;
}

Output:

Entering trace(3), stack address of n: 0x7fff...
Entering trace(2), stack address of n: 0x7fff...
Entering trace(1), stack address of n: 0x7fff...
Entering trace(0), stack address of n: 0x7fff...
Exiting trace(0)
Exiting trace(1)
Exiting trace(2)
Exiting trace(3)

Notice each n has a different address -- these are separate copies on the stack. The function enters in order 3-2-1-0 and exits in reverse: 0-1-2-3.

Fibonacci Sequence

The Fibonacci sequence demonstrates both the elegance and the danger of naive recursion:

#include <stdio.h>

// Naive recursive Fibonacci -- exponential time complexity
int fib_naive(int n) {
    if (n <= 1) return n;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

// Optimized with memoization (dynamic programming)
#define MAX 100
long memo[MAX] = {0};

long fib_memo(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main() {
    printf("Naive fib(10) = %d\n", fib_naive(10));
    printf("Memoized fib(40) = %ld\n", fib_memo(40));
    printf("Memoized fib(50) = %ld\n", fib_memo(50));
    return 0;
}

Output:

Naive fib(10) = 55
Memoized fib(40) = 102334155
Memoized fib(50) = 12586269025

The naive version computes the same values repeatedly. fib_naive(40) calls itself over 300 million times. The memoized version stores results in an array and computes each value once.

Tail Recursion

Tail recursion occurs when the recursive call is the last operation in the function. Some compilers (with optimization flags) can convert tail recursion into a loop, reusing the same stack frame.

#include <stdio.h>

// Not tail recursive -- multiplication happens after recursive call
int fact_normal(int n) {
    if (n <= 1) return 1;
    return n * fact_normal(n - 1);  // Multiplication after recursion
}

// Tail recursive -- recursive call is the last operation
int fact_tail_impl(int n, int accumulator) {
    if (n <= 1) return accumulator;
    return fact_tail_impl(n - 1, n * accumulator);  // Recursion is last
}

int fact_tail(int n) {
    return fact_tail_impl(n, 1);
}

int main() {
    printf("Normal: %d\n", fact_normal(10));
    printf("Tail: %d\n", fact_tail(10));
    return 0;
}

Output:

Normal: 3628800
Tail: 3628800

With GCC optimization (-O2), the tail-recursive version compiles to a loop with no stack growth. The accumulator parameter carries the intermediate result through each call.

Recursion vs Iteration

#include <stdio.h>

// Print array recursively
void print_array_rec(int arr[], int size, int index) {
    if (index >= size) {
        printf("\n");
        return;
    }
    printf("%d ", arr[index]);
    print_array_rec(arr, size, index + 1);
}

// Print array iteratively
void print_array_iter(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int numbers[] = {10, 20, 30, 40, 50};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    printf("Recursive: ");
    print_array_rec(numbers, size, 0);

    printf("Iterative: ");
    print_array_iter(numbers, size);

    return 0;
}

Output:

Recursive: 10 20 30 40 50
Iterative: 10 20 30 40 50

Common Mistakes

1. Missing or incorrect base case: Without a base case, the function recurses infinitely until the stack overflows. Every recursive function must have at least one input that does not trigger a recursive call.

2. Not progressing toward the base case: If the arguments do not change toward the base case, the recursion never terminates. For example, factorial(n) must call factorial(n-1), not factorial(n).

3. Stack overflow from deep recursion: Each recursive call consumes stack memory. A recursion depth of 100,000 typically overflows the stack (1 MB default on Linux). Use iteration for deeply nested problems.

4. Exponential time complexity from redundant calculations: Naive Fibonacci recomputes the same subproblems exponentially. Use memoization or convert to iteration for problems with overlapping subproblems.

5. Modifying global state across recursive calls: If a recursive function modifies a global variable, tracking its state becomes extremely difficult. Pass state as parameters or return values instead.

6. Assuming tail recursion optimization: Not all compilers optimize tail recursion. GCC and Clang do with -O2, but MSVC does not. Rely on iteration for portable performance critical code.

7. Using recursion when iteration is simpler: Array traversal, linear search, and counting are almost always clearer as loops. Reserve recursion for inherently recursive problems: tree traversal, divide-and-conquer, backtracking.

Practice Questions

1. What happens if you call factorial(-1)? How would you fix it?
2. How many stack frames does fib_naive(5) create in total?
3. Why does the tail-recursive factorial use an accumulator parameter?
4. When would you choose recursion over iteration in C?
5. Challenge: Implement a recursive binary search function that finds an element in a sorted array. If found, return its index; otherwise return -1.

Mini Project

Write a recursive directory tree printer:

• Define a function print_tree(const char *path, int depth) that lists all files and directories
• Use opendir, readdir, and stat from <dirent.h> and <sys/stat.h>
• Skip . and .. entries
• Indent each level by depth * 2 spaces
• Print [DIR] prefix for directories and [FILE] prefix for files
• Print file sizes for regular files
• Test on a small directory tree

FAQ

What is Next

Proceed to Variable Arguments to learn how to write functions that accept a variable number of arguments using stdarg.h. Then explore Inline Functions for performance optimization.