Nth Fibonacci

Challenge

Return the n-th Fibonacci number, where each term is the sum of the two before it.

Task

Implement long fib(int n) returning the n-th Fibonacci number, defined by fib(0)=0, fib(1)=1, and fib(k)=fib(k-1)+fib(k-2) for k >= 2. No main — the grader calls it.

Input

One int argument n with n >= 0.

Output

The n-th Fibonacci number as a long.

Example

fib(0)   ->   0
fib(1)   ->   1
fib(10)  ->   55
fib(20)  ->   6765

Edge cases

• fib(0) is 0 and fib(1) is 1.

Rules

• Use an iterative loop, not naive recursion (naive recursion is O(2^n) and too slow for large n).

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.

Input format

One int argument n with n >= 0.

Output format

The n-th Fibonacci number as a long (fib(0)=0, fib(1)=1).

Constraints

Use an iterative O(n) loop, not naive recursion.

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

• Loops: for / while / do-while
• Functions

Up next

• Integer power (iterative)
• Greatest common divisor