Fibonacci Series

Write a recursive function fib(n) that returns the $n$-th Fibonacci number. The sequence is: $F(0) = 0,\; F(1) = 1,\; F(n) = F(n-1) + F(n-2)$ for $n > 1$. Input: 6 → Output: 8. Input: 7 → Output: 13.

Fibonacci has a natural recursive structure: each value depends on the two preceding it. The naive recursive solution mirrors the mathematical definition, but creates a binary tree of calls with many overlapping subproblems (e.g., $F(3)$ is computed multiple times for $F(6)$).

1. Base cases: if $n = 0$, return 0. If $n = 1$, return 1.
2. Recursive case: return $\text{fib}(n-1) + \text{fib}(n-2)$.
3. Each call branches into two sub-calls, creating a binary recursion tree.

• Not having two base cases (both $n = 0$ and $n = 1$ are needed)
• Assuming this approach is efficient — it is $O(2^N)$ and should be memoized for real use
• Off-by-one errors in sequence indexing ($F(6) = 8$ with 0-indexing)
• Confusing Fibonacci with factorial — similar structure, different operations

Naive recursive Fibonacci is intentionally slow. Its purpose is to show how recursion can cause redundant work. This sets the stage for memoization, which reduces complexity to $O(N)$, and dynamic programming.