Fibonacci Series

Write a recursive function fib(n) that returns the n-th Fibonacci number. The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... where F(0) = 0, F(1) = 1, and 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 before it. The naive recursive solution directly mirrors the mathematical definition. However, this creates a binary tree of calls where many subproblems are computed repeatedly (e.g., fib(3) is computed multiple times when calculating fib(6)). This is a classic example of overlapping subproblems.

1. Base cases: if n == 0, return 0. If n == 1, return 1. 2. Recursive case: return fib(n - 1) + 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 optimized with memoization or dynamic programming for real use - Off-by-one errors in the sequence indexing (is fib(6) = 8 or 13? Depends on 0-indexing vs 1-indexing) - Confusing Fibonacci with factorial — they have similar recursive structures but different operations

Naive recursive Fibonacci is intentionally inefficient. The purpose is to understand how recursion can lead to redundant work. This sets the stage for memoization and dynamic programming, which reduce the complexity to O(N). The Fibonacci sequence appears in nature, computer science, and mathematics — mastering it recursively first is essential before optimizing.