Challenge 3: Cached Fibonacci, Verified — Possible Solution
====================================================================

from functools import lru_cache

@lru_cache
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(35))

Output:
9227465

WHY THIS WORKS AS AN ANSWER
------------------------------
This is the exact fibonacci(n) function from this chapter's own
@lru_cache example, applied to a larger input (35 instead of 30) to
make the performance difference more obvious.

Without @lru_cache, this naive recursive implementation recomputes
the same fibonacci(k) value an exponentially growing number of times
— fibonacci(35) alone would trigger millions of redundant calls (for
example, fibonacci(33) gets computed twice, fibonacci(32) four times,
and so on, doubling roughly with each level), making it noticeably
slow, potentially several seconds.

@lru_cache reuses the chapter's own explanation directly: it
remembers the return value for every n it has already computed, so
when the recursion asks for, say, fibonacci(20) a second time (which
happens constantly in this naive recursive structure), the cached
result is returned instantly instead of re-running the whole
recursive computation again. The function's actual logic — the if
n <= 1 base case and the recursive return line — is completely
unchanged; @lru_cache adds the performance improvement purely as a
decorator, with no rewrite needed, exactly the "one line, no logic
change" benefit the chapter highlighted.