python - 递归函数内存使用

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

关于框架内容的好帖子:http://tech.blog.aknin.name/2010/07/22/pythons-innards-interpreter-stacks/