Given n, return F(n), where F(0) = 0, F(1) = 1 and F(n) = F(n − 1) + F(n − 2).
Before you code
Write the one-line recursive version first, and add a counter for the number of calls. Predict the count for n = 30 before running it, using the recursion tree from the lesson.
Hints
- The naive version makes 2 × F(n + 1) − 1 calls: about 2.7 million for n = 30.
- Memoize: keep a dictionary (or
functools.cache) of answers already computed. Now each n is computed once. - Iterate: keep only the last two values and loop from 2 to n. O(n) time, O(1) space.
- Compare the three versions' times for n = 30 and n = 35.
Production & complexity notes
When solving Fibonacci number on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Base cases and recursion trees to reinforce the underlying pattern.
What it practices
Reading cost from a recursion tree and spotting repeated subproblems, from Base cases and recursion trees.