The Fibonacci sequence starts with 0 and 1, and each number after that is the sum of the two before it. So F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, F(4) = 2 + 1 = 3, and the sequence runs 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .... Return the number at position n.

The definition F(n) = F(n-1) + F(n-2) is already recursive, so it fits a self-calling function. The recursive step reaches back two positions, not one, so it needs two anchored values to start from rather than a single base case.

Key Constraints:

Intuition

The definition translates straight into code: fib(n) returns fib(n - 1) + fib(n - 2), letting the same function resolve each smaller piece.

The base cases are fib(0) = 0 and fib(1) = 1. Without both, a call like fib(2) would eventually ask for fib(0) and have no value to return. Every call lowers n, so the chain always bottoms out at 0 or 1.

The cost is in the overlap. Computing fib(5) asks for fib(4) and fib(3), but fib(4) also asks for fib(3), so fib(3) is computed twice, fib(2) several times, and so on. The number of calls roughly doubles with each increase in n, giving this version exponential running time. Approach 2 fixes that.

Algorithm

Example Walkthrough

Input:

To find fib(5), the call needs fib(4) + fib(3). Resolving fib(4) needs fib(3) + fib(2), and fib(3) needs fib(2) + fib(1). The branches keep splitting until they reach fib(1) = 1 and fib(0) = 0, which return directly. Adding back up: fib(2) is 1, fib(3) is 2, fib(4) is 3, and fib(5) is 3 + 2 = 5. Notice that fib(3) was evaluated more than once along the way, once inside fib(5) and again inside fib(4), which is the repeated work that makes this approach slow.

Code

Intuition

The exponential cost comes entirely from recomputing the same Fibonacci numbers. The fix is to build the sequence forward and keep only the two most recent values, since that is all the next number depends on. Start with F(0) = 0 and F(1) = 1, then slide the pair upward one step at a time. Each step computes the next number as the sum of the two current ones, then shifts the window forward.

Algorithm

Example Walkthrough

Input:

The pair starts as prev = 0 and curr = 1. At step 2, next = 0 + 1 = 1, so the pair becomes prev = 1, curr = 1. At step 3, next = 1 + 1 = 2, giving prev = 1, curr = 2. At step 4, next = 1 + 2 = 3, giving prev = 2, curr = 3. At step 5, next = 2 + 3 = 5, giving curr = 5. The loop has reached n, so it returns 5. Each Fibonacci number was computed exactly once, in order, which is why this version is fast.

Code