Recursion in C

Recursion is a technique where a function calls itself to solve a problem. Every recursive function must have:

1. A base case — condition to stop recursion
2. A recursive case — the function calling itself with a smaller input

---

How Recursion Works

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

Trace for factorial(4):

factorial(4)
  → 4 * factorial(3)
       → 3 * factorial(2)
            → 2 * factorial(1)
                 → 1  (base case)
            → 2 * 1 = 2
       → 3 * 2 = 6
  → 4 * 6 = 24

---

Classic Recursive Programs

Fibonacci Series

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

/* fibonacci(0)=0, fibonacci(1)=1, fibonacci(5)=5 */

Power Function

int power(int base, int exp) {
    if (exp == 0)
        return 1;
    return base * power(base, exp - 1);
}

Sum of Digits

int sumDigits(int n) {
    if (n == 0)
        return 0;
    return (n % 10) + sumDigits(n / 10);
}

---

Recursion vs Iteration

---

Tower of Hanoi (Classic Exam Problem)

#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);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

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

Note: For n disks, Tower of Hanoi requires 2ⁿ - 1 moves.