Nth Fibonacci Number (Memoized)

Problem Statement

You're given a non-negative integer n. Compute the nth number in the Fibonacci sequence, using 0-indexing, where fib(0) = 0, fib(1) = 1, and every later term is the sum of the two terms directly before it (fib(k) = fib(k - 1) + fib(k - 2)). The catch is efficiency: n can be as large as 35, and the most obvious recursive solution recomputes the same values so many times that it becomes noticeably slow at that size, so your solution needs to avoid that repeated work.

Input Format

The input is a single line containing one integer n, where 0 <= n <= 35. There is no other input.

Output Format

Print a single line containing fib(n), the nth Fibonacci number, as an integer. Print nothing else.

Example Walkthrough

Take the sample input 6. Rather than recursing, imagine filling in an array dp where dp[i] will hold fib(i), starting from the two known base cases and moving upward. dp[0] = 0 and dp[1] = 1 by definition. Then dp[2] = dp[0] + dp[1] = 0 + 1 = 1. dp[3] = dp[1] + dp[2] = 1 + 1 = 2. dp[4] = dp[2] + dp[3] = 1 + 2 = 3. dp[5] = dp[3] + dp[4] = 2 + 3 = 5. Finally dp[6] = dp[4] + dp[5] = 3 + 5 = 8. Since the input was 6, we print dp[6], which is 8 — matching the expected output. Notice that each value was computed exactly once and reused by the next step, rather than being recalculated from scratch.

Approach

Write the recursive definition directly and it looks appealingly simple: fib(n) = fib(n-1) + fib(n-2), with fib(0) and fib(1) as base cases. The problem is what that recursion actually does underneath. Trace the calls made by fib(5): it calls fib(4) and fib(3). fib(4) in turn calls fib(3) and fib(2) — so fib(3) is now being computed twice, once as a direct child of fib(5) and once as a child of fib(4), and those two computations know nothing about each other. Keep expanding and it gets worse: fib(2) ends up called three separate times across this small tree (once under each of the two fib(3) calls, and once directly under fib(4)), and fib(1) and fib(0) are recomputed even more often than that. There are really only 6 distinct subproblems here (fib(0) through fib(5)), but the naive recursion tree makes far more calls than that by re-deriving the same answers over and over. As n grows, this duplication compounds at every level, and the total number of calls grows exponentially in n (it's bounded above by 2^n) — which is why naive recursion becomes painfully slow well before n reaches 35, even though the underlying math is trivial.

The fix is to make sure each distinct subproblem is only ever solved once. One way is memoization: keep a cache (a dictionary works well) that maps an index k to its already-computed fib(k). Before doing any recursive work for fib(k), check the cache first; if it's there, return it immediately; if not, compute it recursively, store the result in the cache, and then return it. The recursive structure of the code stays exactly as simple as the naive version — the only change is that repeated calls become cheap cache lookups instead of full recomputations. An equally valid alternative is to abandon recursion entirely and build the sequence bottom-up: start from fib(0) and fib(1), and repeatedly compute the next term from the previous two in a simple loop until you reach n. Both approaches do the same fundamental amount of work — one computation per distinct index from 0 to n — which is what brings the running time down from exponential to linear.

Either technique is a legitimate solution here. Top-down memoized recursion mirrors the recursive definition most directly and is often the more natural first attempt if you already tried plain recursion; bottom-up iteration avoids recursion (and its call-stack overhead) altogether and is usually the simpler, more efficient choice once you see the pattern.

Common Mistakes

• Mixing up the two common versions of the Fibonacci sequence. Some sources start it as "1, 1, 2, 3, 5, ..." rather than "0, 1, 1, 2, 3, 5, ...". This problem is explicitly 0-indexed with fib(0) = 0, so treating n = 0 as if it should return 1 is a wrong answer here, even though it happens to be right for n = 1 (where the two conventions agree).
• "Memoizing" in a way that doesn't actually persist the cache. If a cache dictionary is created fresh inside the recursive helper function itself (instead of outside it, or passed through the calls), every recursive call starts with an empty cache again and none of the memoization actually happens — the code looks like it should be fast but still does the full exponential amount of work.
• Off-by-one errors in an iterative loop's range. A loop that runs one iteration too few ends up returning fib(n - 1) instead of fib(n), and one that runs one too many returns fib(n + 1) instead. This is easy to miss because it only shows up as a wrong number, not a crash, so it's worth double-checking a loop-based solution against a couple of known values (like fib(0) = 0 and fib(6) = 8) by hand.