python - 了解递归调用中的 Python 列表内存使用情况

Question

我只是想检查一下我是否正确理解了 Python 的内存管理。

以下函数将使用 O(j) 内存，但不会 O(nj) 内存，因为参数 n 是对列表的引用，而不是列表本身。

def cool(n,j):
    if j == 0:
        return
    return cool(n,j-1)

此外，假设这个函数是用 C 编写的，我假设使用 C 时它的内存使用量是 O(nj) 是否正确，因为列表/数组的副本是为每个递归调用创建。

Answer 1

是的，没错。每个递归步骤将使用 O(1) 内存:函数调用开销，每个函数参数一个指针。

您可以通过创建一个大对象 (x = "x"* 1024 * 1024 * 100) 来实验验证这一点，然后对其进行多次递归并检查进程的内存使用情况:

def recurse(x, n):
    if n == 0:
        raw_input("done! Check memory usage now.")
        return
    return recurse(x, n - 1)

recurse(x, 1000)