递归函数内存使用情况

Question

我这里有一个递归函数：

def pow(x, n):
    if n == 0:
       return 1
    else:
       return x * pow(x, n-1)
answer = pow(a, b)

以及迭代：

def pow(x, n): # n != 0
    answer = x
    while n > 1:
        answer *= x
        n -= 1
    return answer
answer = pow(a, b)

我想知道它们中哪一个使用更多内存。我认为递归使用更多内存，因为它为每个函数调用保留传递的“变量”。如果这是正确的，那么解释这一点的形式主义是什么？有没有一种很好的方法来跟踪代码内的内存使用情况？

我不认为这是重复的。主要问题不是关于跟踪内存使用情况，而是关于递归内存使用情况。

Answer 1

这里不需要形式主义。

Python 栈帧非常巨大。

您的递归代码使用了更多内存。

典型的 CPython 堆栈帧有超过 50 个元素加上局部变量，以 x86_64 架构为例，几乎有 500 个字节。

In [1]: import inspect

In [2]: inspect.stack()[1][0]
Out[2]: <frame at 0x7fed81c86850>

In [3]: inspect.stack()[1][0].__sizeof__()
Out[3]: 472