Unit 08 — Recursion

🪞 The mirror analogy

Stand between two mirrors facing each other. You see yourself reflected, and inside that reflection you see another reflection, and inside that another — going smaller and smaller until they become too small to see.

Recursion works the same way. Each call creates a smaller version of itself, which creates an even smaller one, going deeper and deeper — until we hit the base case (the point where the mirrors end) and start coming back.

#include <stdio.h>
 
int factorial(int n) {
    /* base case: factorial of 0 is 1 — stop here */
    if (n == 0) {
        return 1;
    }
 
    /* recursive case: n! = n × (n-1)! */
    return n * factorial(n - 1);
}
 
int main() {
    printf("factorial(0) = %d\n", factorial(0));  /* 1 */
    printf("factorial(1) = %d\n", factorial(1));  /* 1 */
    printf("factorial(5) = %d\n", factorial(5));  /* 120 */
    printf("factorial(7) = %d\n", factorial(7));  /* 5040 */
    return 0;
}

#include <stdio.h>
 
int fibonacci(int n) {
    /* two base cases */
    if (n == 0) return 0;
    if (n == 1) return 1;
 
    /* recursive case: sum of the two before it */
    return fibonacci(n - 1) + fibonacci(n - 2);
}
 
int main() {
    int i;
    printf("Fibonacci sequence: ");
    for (i = 0; i < 10; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    /* Output: 0 1 1 2 3 5 8 13 21 34 */
    return 0;
}

⚠ Why this is dangerously slow

Computing fib(5) looks harmless — but look at how many times the same values get computed repeatedly:

#include <stdio.h>
 
int sumOfDigits(int n) {
    /* base case: no digits left */
    if (n == 0) return 0;
 
    /* recursive case: last digit + sum of remaining digits */
    return (n % 10) + sumOfDigits(n / 10);
    /* n % 10 gives the last digit: 1234 % 10 = 4 */
    /* n / 10 removes the last digit: 1234 / 10 = 123 */
}
 
int main() {
    printf("sumOfDigits(1234) = %d\n", sumOfDigits(1234)); /* 10 */
    printf("sumOfDigits(9999) = %d\n", sumOfDigits(9999)); /* 36 */
    printf("sumOfDigits(100)  = %d\n", sumOfDigits(100));  /* 1 */
    return 0;
}

#include <stdio.h>
 
/* Simple version — O(n) */
int power(int base, int exp) {
    if (exp == 0) return 1;            /* x^0 = 1 — base case */
    return base * power(base, exp - 1); /* x^n = x × x^(n-1) */
}
 
/* Fast version — O(log n) — splits the problem in half each time */
int fastPower(int base, int exp) {
    if (exp == 0) return 1;
 
    if (exp % 2 == 0) {
        /* even exponent: x^n = (x^(n/2))^2 */
        int half = fastPower(base, exp / 2);
        return half * half;  /* compute half once, use twice */
    } else {
        /* odd exponent: x^n = x × x^(n-1) */
        return base * fastPower(base, exp - 1);
    }
}
 
int main() {
    printf("2^10  = %d\n", power(2, 10));      /* 1024 */
    printf("3^4   = %d\n", power(3, 4));        /* 81 */
    printf("2^10  = %d (fast)\n", fastPower(2, 10)); /* 1024 */
    printf("2^20  = %d (fast)\n", fastPower(2, 20)); /* 1048576 */
    return 0;
}

#include <stdio.h>
 
int gcd(int a, int b) {
    /* base case: when b is 0, GCD is a */
    if (b == 0) return a;
 
    /* recursive case: GCD(a, b) = GCD(b, a % b) */
    return gcd(b, a % b);
}
 
int main() {
    printf("GCD(12, 8)  = %d\n", gcd(12, 8));   /* 4 */
    printf("GCD(48, 18) = %d\n", gcd(48, 18));  /* 6 */
    printf("GCD(100, 75)= %d\n", gcd(100, 75)); /* 25 */
    return 0;
}

/* Recursive factorial — elegant, uses call stack */
int factorialRecursive(int n) {
    if (n == 0) return 1;
    return n * factorialRecursive(n - 1);
}
 
/* Iterative factorial — uses a loop, no extra stack space */
int factorialIterative(int n) {
    int result = 1;
    int i;
    for (i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
 
/* Both give identical answers — different tradeoffs:
   Recursive: cleaner code, O(n) space (call stack)
   Iterative: slightly more code, O(1) space (just one variable)
*/

Step 1 and Step 3 are the recursive calls — the same problem on n-1 disks. Step 2 is the base work. When n = 1 (just one disk), move it directly — that is the base case. The magic: you never need to think about which specific disk goes where. Just trust the three steps — recursion handles all the details.

#include <stdio.h>
 
/*
 * hanoi(n, source, target, helper)
 * Move n disks from source rod to target rod, using helper rod
 */
void hanoi(int n, char source, char target, char helper) {
    /* base case: only one disk — move it directly */
    if (n == 1) {
        printf("Move disk 1 from rod %c to rod %c\n", source, target);
        return;
    }
 
    /* step 1: move top n-1 disks from source to helper */
    hanoi(n - 1, source, helper, target);
 
    /* step 2: move the largest disk from source to target */
    printf("Move disk %d from rod %c to rod %c\n", n, source, target);
 
    /* step 3: move n-1 disks from helper to target */
    hanoi(n - 1, helper, target, source);
}
 
int main() {
    printf("Tower of Hanoi with 3 disks:\n");
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

/* Output for n=3 (7 moves — minimum possible):
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C
*/