Recursion in C

Recursion is a programming technique where a function calls itself to solve a problem. The function keeps calling itself with a smaller version of the same problem until it reaches a simple case that can be solved directly. That simple case is called the base case.

Think of recursion like a mirror facing another mirror — you see an image within an image, getting smaller and smaller. Recursion works the same way: each function call creates a slightly smaller problem until the smallest possible version is reached and solved.

Key Components of Recursion

1. Base Case: The condition that stops the recursion. Without it, the function calls itself forever (infinite recursion), causing a stack overflow error.
2. Recursive Case: The part where the function calls itself with a modified (usually smaller) argument, moving closer toward the base case.

How Recursion Works — The Call Stack

Every time a function is called in C, a new stack frame is created in memory to hold its local variables and return address. When a recursive function calls itself, a new stack frame is pushed on top. When the base case is reached, functions start returning and stack frames are popped one by one.

Simple Example — Countdown

#include <stdio.h>

void countdown(int n)
{
    if (n == 0)             // Base case
    {
        printf("Go!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);       // Recursive call with smaller value
}

int main()
{
    countdown(5);
    return 0;
}

Output

5
4
3
2
1
Go!

Example 1 — Factorial Using Recursion

The factorial of a number n is the product of all positive integers from 1 to n.

Factorial of 5 = 5 × 4 × 3 × 2 × 1 = 120

Mathematical Definition

factorial(0) = 1              (base case)
factorial(n) = n * factorial(n-1)  (recursive case)

#include <stdio.h>

int factorial(int n)
{
    if (n == 0 || n == 1)   // Base case
        return 1;

    return n * factorial(n - 1);  // Recursive call
}

int main()
{
    int num = 5;
    printf("Factorial of %d = %d\n", num, factorial(num));
    return 0;
}

Output

Factorial of 5 = 120

How the Calls Unfold

factorial(5)
  = 5 * factorial(4)
       = 4 * factorial(3)
            = 3 * factorial(2)
                 = 2 * factorial(1)
                      = 1  (base case returns 1)
                 = 2 * 1 = 2
            = 3 * 2 = 6
       = 4 * 6 = 24
  = 5 * 24 = 120

Example 2 — Fibonacci Series Using Recursion

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each number is the sum of the two preceding numbers.

#include <stdio.h>

int fibonacci(int n)
{
    if (n == 0) return 0;   // Base case 1
    if (n == 1) return 1;   // Base case 2
    return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive case
}

int main()
{
    printf("Fibonacci sequence (first 8 terms):\n");
    for (int i = 0; i < 8; i++)
    {
        printf("%d ", fibonacci(i));
    }
    printf("\n");

    return 0;
}

Output

Fibonacci sequence (first 8 terms):
0 1 1 2 3 5 8 13 

Example 3 — Sum of Digits Using Recursion

#include <stdio.h>

int sumOfDigits(int n)
{
    if (n == 0) return 0;       // Base case
    return (n % 10) + sumOfDigits(n / 10);
}

int main()
{
    int num = 1234;
    printf("Sum of digits of %d = %d\n", num, sumOfDigits(num));
    // 1+2+3+4 = 10
    return 0;
}

Output

Sum of digits of 1234 = 10

Example 4 — Power of a Number

Calculate base^exponent using recursion.

#include <stdio.h>

int power(int base, int exp)
{
    if (exp == 0) return 1;     // Base case: anything^0 = 1
    return base * power(base, exp - 1);
}

int main()
{
    printf("2^10 = %d\n", power(2, 10));  // 1024
    printf("3^4  = %d\n", power(3, 4));   // 81
    return 0;
}

Output

2^10 = 1024
3^4  = 81

Example 5 — Reverse a Number

#include <stdio.h>

void reverseNumber(int n)
{
    if (n == 0) return;     // Base case
    printf("%d", n % 10);  // print last digit
    reverseNumber(n / 10); // recursive call with remaining digits
}

int main()
{
    printf("Reverse of 12345: ");
    reverseNumber(12345);
    printf("\n");
    return 0;
}

Output

Reverse of 12345: 54321

Recursion vs Iteration

Towers of Hanoi — Classic Recursion Problem

The Tower of Hanoi is a classic puzzle involving 3 pegs and N disks. The goal is to move all disks from peg A to peg C using peg B as helper, never placing a larger disk on a smaller one.

#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);  // move n-1 disks from A to B using C
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, via, to, from);  // move n-1 disks from B to C using A
}

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

Output

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

Common Mistakes in Recursion

• Missing Base Case: Without a base case, the function calls itself forever, causing a stack overflow crash.
• Wrong Base Case: An incorrect base case gives wrong results.
• Not Moving Toward Base Case: If the recursive call doesn't bring the argument closer to the base case, recursion never ends.

Summary

Recursion is a powerful technique where a function solves a problem by solving smaller versions of the same problem. Every recursive solution must have a base case to stop the recursion and a recursive case that moves toward the base case. Recursion is elegant and natural for problems like factorials, Fibonacci, tree traversal, and Towers of Hanoi. However, it uses more memory than loops due to the call stack. Choosing between recursion and iteration depends on the nature of the problem and performance requirements.