Fibonacci Number

Problem

Recommendation engines and mathematical libraries frequently compute Fibonacci numbers as a building block for sequence generation and golden ratio approximations. Given n, return F(n) where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2). The naive recursive approach has exponential time; your task is to implement the efficient memoized version.

Input: n = 0  → 0
Input: n = 1  → 1
Input: n = 6  → 8
Input: n = 10 → 55

Solution

Approach: Top-down recursion with memoization (the @functools.lru_cache decorator).

The recurrence is the textbook definition: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1 returned directly (the n <= 1 base case returns n for both). Written naively, this branches into two calls per level, and the same subproblem reappears in many branches - fib(4) calls fib(3) and fib(2), but fib(3) also calls fib(2), so fib(2) is recomputed. That overlap multiplies into an O(2^n) call tree. The fix is to remember each answer the first time it is computed. @functools.lru_cache(maxsize=None) wraps the function in a cache keyed by argument: the first time fib(k) runs, its result is stored; every later call with the same k returns the stored value in O(1) without recursing.

The key insight is that there are only n+1 distinct subproblems - fib(0) through fib(n). Memoization guarantees each is computed exactly once, so the exponential tree collapses to a linear chain of real work plus constant-time cache hits filling the second branch of every node. Trace fib(6): the first descent computes fib(6), fib(5), ..., fib(0) once each, and every fib(n-2) call after that is a cache hit, giving 0, 1, 1, 2, 3, 5, 8.

Edge cases: fib(0) and fib(1) are handled by the single n <= 1 guard returning n, so no special-casing is needed. The cache persists across top-level calls, so a later fib(30) reuses work from earlier calls.

Complexity: O(n) time, O(n) space - each of the n+1 subproblems is solved once, and the cache plus the n-deep first descent both hold O(n) entries.