C Recursion

What is Recursion?

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. Every recursive solution has two parts:

Base case — the condition that stops the recursion (prevents infinite loop).
Recursive case — the function calls itself with a simpler/smaller input.

Each recursive call is pushed onto the call stack. When the base case is reached, the calls unwind and return their results back up the chain.

Warning: A recursive function without a proper base case will cause a stack overflow — the program crashes when the call stack runs out of memory.

Factorial — Classic Recursion Example

Factorial of n (written n!) = n Ã— (n-1) Ã— (n-2) Ã— ... Ã— 1. Base case: 0! = 1.

Factorial — Recursive vs Iterative

#include <stdio.h>

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

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

/*
Call trace for factorial(4):
  factorial(4) â†’ 4 * factorial(3)
    factorial(3) â†’ 3 * factorial(2)
      factorial(2) â†’ 2 * factorial(1)
        factorial(1) â†’ 1  (base case)
      factorial(2) â†’ 2 * 1 = 2
    factorial(3) â†’ 3 * 2 = 6
  factorial(4) â†’ 4 * 6 = 24
*/

#include <stdio.h>

long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

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

/*
Iterative is generally faster (no function call overhead)
and safer (no stack overflow risk for large n).
*/

Fibonacci Sequence

Fibonacci: F(0)=0, F(1)=1, F(n) = F(n-1) + F(n-2). This is a classic example that shows both the elegance and the inefficiency of naive recursion — it recalculates the same values many times.

Fibonacci — Naive vs Memoized

#include <stdio.h>

// Naive: O(2^n) — exponential time, very slow for large n
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

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

/*
fib(5) call tree (shows repeated work):
fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) â† computed again!
│   │   └── fib(1)
│   └── fib(2)     â† computed again!
└── fib(3)         â† computed again!
*/

#include <stdio.h>
#define MAX 100

long long memo[MAX];  // cache array, initialized to -1

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // return cached result
    memo[n] = fib(n - 1) + fib(n - 2); // compute and cache
    return memo[n];
}

int main() {
    for (int i = 0; i < MAX; i++) memo[i] = -1;  // init cache

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

// Memoized: O(n) — each value computed only once

Tower of Hanoi

Tower of Hanoi is the perfect recursion problem. Move n disks from source peg to destination peg using an auxiliary peg, with the rule that a larger disk can never be placed on a smaller one.

Tower of Hanoi

#include <stdio.h>

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

int main() {
    int n = 3;
    printf("Tower of Hanoi with %d disks:\n\n", n);
    hanoi(n, '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

Total moves for n disks = 2^n - 1
For n=3: 2^3 - 1 = 7 moves
*/

Recursion vs Iteration — When to Use Each

Aspect	Recursion	Iteration
Code clarity	Cleaner for tree/graph problems	Cleaner for simple loops
Performance	Slower (function call overhead)	Faster
Memory	Uses call stack (risk of overflow)	Uses constant stack space
Best for	Tree traversal, divide & conquer, backtracking	Simple counting, array traversal
Debugging	Harder to trace	Easier to trace

Previous Next

C Recursion

What is Recursion?

Factorial — Classic Recursion Example

Fibonacci Sequence

Tower of Hanoi

Recursion vs Iteration — When to Use Each

Ready to Level Up Your Skills?