为什么我的递归函数更新列表（计算 n 的斐波那契）

Question

我正在尝试学习动态规划。我已经通过一个示例说明如何查找输入 n 的斐波那契数，同时缓存每个 "new" 调用的结果。

我理解函数递归调用的顺序：fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(1) -> fib(0) -> fib(1) -> fib(2) "Cache found" -> fib(3) "Cache found" 对于 n = 5

我很难理解最后的 fib(2) 和 fib(3) 调用是如何访问更新的缓存的，因为每次调用只 returns 一个整数，而不是列表，我不知道'认为我已将列表声明为全局变量。

我最初希望列表在我的代码中表现得像整数 x，因此欢迎解释这些值是如何传回的。

代码：

def fib(n, cache, x):
    print(n, cache)
    print("x: ", x)
    x += 1
    if n == 0 or n == 1:
        return n

    if cache[n] == 0:
        cache[n] = fib(n-1, cache, x) + fib(n-2, cache, x)
    else:
        print("Cache called on", n)

    return cache[n]


def main():
    n = 5
    x = 0
    cache = [0 for _ in range(n+1)]
    print(fib(n, cache, x))
    print(cache)
    print("x: ", x)


if __name__ == "__main__":
    main()

输出：

5 [0, 0, 0, 0, 0, 0]
x:  0
4 [0, 0, 0, 0, 0, 0]
x:  1
3 [0, 0, 0, 0, 0, 0]
x:  2
2 [0, 0, 0, 0, 0, 0]
x:  3
1 [0, 0, 0, 0, 0, 0]
x:  4
0 [0, 0, 0, 0, 0, 0]
x:  4
1 [0, 0, 1, 0, 0, 0]
x:  3
2 [0, 0, 1, 2, 0, 0]
x:  2
Cache called on 2
3 [0, 0, 1, 2, 3, 0]
x:  1
Cache called on 3
5
[0, 0, 1, 2, 3, 5]
x:  0

Answer 1

您传递了 cache 的原件，而不是副本（新建对象）。因此，fib 的每个实例都与 相同的 对象一起工作。一个实例中的更新立即可供其他实例使用。另见 here。

Answer 2

在 python 中，函数参数是 "passed-by-object"（或传递对象引用）。这意味着如果将列表（可变对象）传递给函数，则可以修改列表的元素。但是，如果您将通过新列表分配列表，那么该列表将不会在调用者的范围内发生变化。

def list_scope(l):
    print(l, "id: ", id(l))
    l = [3, 4,5]
    print(l, "id: ", id(l))

def main():
    l = [1, 2, 3]
    print("id: ", id(l))
    list_scope(l)
    print("id: ", id(l))

main()

输出：

id: 4510275784
[1, 2, 3] id:  4510275784
[3, 4, 5] id:  4509275592
id: 4510275784

分配列表 [3, 4, 5] 之前 list_scope 中 l 的 ID 与 main 中的 ID 相同。一旦 [3, 4, 5] 被分配，它就会改变，但在 main.

中保持不变

为什么我的递归函数更新列表（计算 n 的斐波那契）

Why is my recursive function updating a list (calculating fibonacci of n)

python

recursion

memoization

dynamic-programming

fibonacci