关于带Memoization的斐波那契算法执行顺序及缓存复用的疑问

Great question—this is a common point of confusion when moving from a language like C to Python, so let's unpack this step by step.

First, let's clean up the code for readability:

def dynamic_fib(n):
    return fibonacci(n, {})

def fibonacci(n, dic):
    if n == 0 or n == 1:
        return n
    if not dic.get(n, False):
        dic[n] = fibonacci(n-1, dic) + fibonacci(n-2, dic)
    return dic[n]

The Core Reason: Python Passes Mutable Objects by Reference #

Here's what you're missing: in Python, mutable objects (like dictionaries, lists, and custom classes) are passed by object reference, not by value. That means when you pass dic to a recursive call of fibonacci, you're not sending a copy of the dictionary—you're sending a reference to the exact same dictionary object that lives in memory.

Let's walk through the dynamic_fib(4) call to see this in action:

1. dynamic_fib(4) creates a single empty dictionary {} and passes it to fibonacci(4, dic).
2. fibonacci(4, dic) checks if 4 is in the dict (it's not), so it calls fibonacci(3, dic) + fibonacci(2, dic).
3. First, fibonacci(3, dic) runs: it checks for 3 (not present), so it calls fibonacci(2, dic) + fibonacci(1, dic).
4. fibonacci(2, dic) runs: no entry for 2, so it calls fibonacci(1, dic) (returns 1) and fibonacci(0, dic) (returns 0). It adds dic[2] = 1 + 0 = 1 to the shared dictionary (now {2: 1}) and returns 1.
5. Back to fibonacci(3, dic): fibonacci(1, dic) returns 1, so it adds dic[3] = 1 + 1 = 2 to the same dictionary (now {2: 1, 3: 2}) and returns 2.
6. Now we get to the right-hand call in fibonacci(4, dic): fibonacci(2, dic). This time, when it checks the dictionary, 2 is already there (value 1)! It doesn't need to recalculate—just returns 1 immediately.
7. Finally, fibonacci(4, dic) adds dic[4] = 2 + 1 = 3 and returns 3.

How This Differs from C #

In C, if you passed a struct or array by value, each function would get its own copy—so changes in one stack frame wouldn't affect others. But when you use & to pass a pointer, you're doing the exact same thing Python does automatically for mutable objects: letting all functions operate on the same chunk of memory.

Python doesn't require explicit pointer syntax like & because it handles reference semantics for mutable objects behind the scenes. The dictionary isn't trapped in a single stack frame—it's a single object that all recursive calls can read and modify.

Key Takeaway #

The cache works because every recursive call to fibonacci uses the same dictionary instance. When one call adds a value to dic, all subsequent calls (even those in different stack frames) can access that value immediately.

内容的提问来源于stack exchange，提问作者Matt Choi