Recursion, Fibonacci and TOH

Recursion

Recursion is a method where a function calls itself with smaller input until a base case is reached. Each call keeps its own parameters and local variables on the stack. A recursive function needs (1) a base case and (2) a recursive case that moves toward the base case.

Iterative or recursive for Fibonacci?

I prefer the iterative algorithm.

int fibr(int n) { return n <= 1 ? n : fibr(n-1) + fibr(n-2); }   /* recursive */

int fibi(int n) {                                                /* iterative */
    int a = 0, b = 1, c;
    if (n == 0) return 0;
    for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; }
    return b;
}

Reasons:

• The recursive version recomputes the same values many times: fib(5) makes 15 calls and fib(30) makes 2,692,537 calls (counted by program), so time is exponential O(2ⁿ).
• Recursion uses O(n) stack space; the loop uses O(1).
• The iterative version takes only n steps, O(n).

              fib(4)
            /        \
        fib(3)       fib(2)
        /    \       /    \
    fib(2) fib(1) fib(1) fib(0)
    /   \
 fib(1) fib(0)        fib(2) is computed twice

Tower of Hanoi

Three pegs A, B, C and n disks on A (largest at bottom). Move all to C, one disk at a time, never putting a larger disk on a smaller one.

Solution: move n-1 disks A→B (using C), move disk n A→C, move n-1 disks B→C (using A).

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

Moves needed = 2ⁿ − 1. For n = 3: A→C, A→B, C→B, A→C, B→A, B→C, A→C (7 moves). TOH is a case where recursion is preferred because the iterative solution is much harder to write.