Nth Fibonacci

Challenge

Implement long fib(int n) returning the n-th Fibonacci number where fib(0)=0, fib(1)=1.

Why this matters

Fibonacci is the canonical recursive vs iterative comparison. The recursive version takes O(2^n); the iterative version is O(n). It's a great way to feel the difference.

Starter code

long fib(int n) {
    /* TODO */
    return 0;
}

Common mistakes

Using naive recursion for large n (it takes forever). Starting from F(0)=0 vs F(1)=1 inconsistently. Overflowing int at F(47).

Edge cases to handle

F(0) = 0, F(1) = 1 (definition). F(47) overflows int.

Complexity

O(n) iterative. O(phi^n) ≈ O(1.618^n) naive recursive.

Background lessons

• for / while / do-while
• Functions

Up next

• Integer power (iterative)
• Greatest common divisor