我注意到，在我的机器上，以下代码达到了n = 2960的最大递归深度:
m = {0:0, 1:1}
def f(n):
if n not in m:
m[n] = f(n - 1) + f(n - 2)
return m[n]
当此版本达到n = 988时:
m = {0:0, 1:1}
def f(n):
if n not in m:
m[n] = sum(f(n - i) for i in [1, 2])
return m[n]
有谁能解释"引擎盖下"发生了什么吗?这就解释了这种差异吗?
更准确地说，理解为什么这个例子中的因子是3，并且能够推导出包含更多项的求和，这将是非常好的。
TL;DR:sum是一个额外的函数调用，它所求和的生成器表达式也是用嵌套函数作用域(docs)
因此，第二种方法在递归期间使用两个额外的堆栈帧，以及递归调用本身，这解释了这里的因子3。…推导式在单独的隐式嵌套作用域中执行。这确保了在目标列表中分配的名称不会"泄漏"到封闭范围内。
请注意，默认的递归限制是1000，因此您应该看到第一种情况的堆栈溢出正好为1000，第二种情况的堆栈溢出为334(在Python 3.10或更低版本上)。要获得2960和988，您可以输入:
- 进口了
sys.setrecursionlimit(3000)， - 已经在某处花费了几个堆栈帧。
例如，在IDE或精心设计的交互式REPL中运行此代码可能会完成上述两项任务。
近期动态:
有PEP 709 -内联推导式，它是关于从推导式中删除这个隐藏函数的。生成器表达式目前没有内联到PEP的参考实现中，尽管将来可能会考虑。
CPython 3.11已经进行了一些优化，以减少代码中函数调用的数量，这改变了堆栈溢出的点。它将发生在501而不是CPython 3.11中的334。原因在Python 3.11新增功能:内联Python函数调用。
我也将在这里添加我的调试。在运行了一些测试之后，我发现traceback模块给了我一个明显(~333)小于递归限制的调用堆栈。我注意到这个差异总是接近调用堆栈上的<genexpr>调用的数量:
import sys
import traceback
from collections import Counter
from pprint import pprint
sum_every_n = int(sys.argv[1])
def f(n=0):
try:
if n % sum_every_n == 0:
return sum(f(n+i) for i in [1,2])
else:
return f(n+1) + f(n+2)
except RecursionError:
stack = traceback.extract_stack()
counts = Counter([frame.name for frame in stack])
stack_size = len(stack)
stack_size_plus = stack_size + counts['<genexpr>']
pprint(counts)
print(f'rec limit: {sys.getrecursionlimit()}')
print(f'stack size: {stack_size}')
print(f'adj stack size: {stack_size_plus}')
sys.exit()
f()
以下是sum_every_n的一些值的结果:
$ ./rec3.py 1
Counter({'f': 333, '<genexpr>': 332, '<module>': 1})
rec limit: 1000
stack size: 666
adj stack size: 998
$ ./rec3.py 2
Counter({'f': 499, '<genexpr>': 249, '<module>': 1})
rec limit: 1000
stack size: 749
adj stack size: 998
$ ./rec3.py 3
Counter({'f': 599, '<genexpr>': 200, '<module>': 1})
rec limit: 1000
stack size: 800
adj stack size: 1000
$ ./rec3.py 4
Counter({'f': 665, '<genexpr>': 166, '<module>': 1})
rec limit: 1000
stack size: 832
adj stack size: 998
似乎生成器确实向堆栈中添加了一个函数调用，但每个生成器表达式也算作调用堆栈中的两个函数。这就解释了你原来问题中的比例。虽然不确定为什么会这样，但我欢迎任何可能的解释!
一个令人着迷的行为，我没有找到问题的根源，但我仍然想分享一些我写的日志代码，可能会帮助其他人找到问题:
m = {0:0, 1:1}
def f(n, depth=0):
print(f"{' '*depth}f({n})")
if n not in m:
print(f"{' '*depth}Computing f({n-1}) + f({n-2})")
m[n] = sum(f(n - i, depth+1) for i in [1, 2])
else:
print(f"{' '*depth}Already computed f({n})")
return m[n]
print("Testing the version with the iterator, call stack is:")
f(10)
m = {0:0, 1:1}
def g(n, depth=0):
print(f"{' '*depth}g({n})")
if n not in m:
print(f"{' '*depth}Computing g({n-1}) + g({n-2})")
m[n] = g(n - 1, depth+1) + g(n - 2, depth+1)
else:
print(f"{' '*depth}Already computed g({n})")
return m[n]
print("Testing the version with the normal sum, call stack is:")
g(10)
输出为:
Testing the version with the iterator, call stack is:
f(10)
Computing f(9) + f(8)
f(9)
Computing f(8) + f(7)
f(8)
Computing f(7) + f(6)
f(7)
Computing f(6) + f(5)
f(6)
Computing f(5) + f(4)
f(5)
Computing f(4) + f(3)
f(4)
Computing f(3) + f(2)
f(3)
Computing f(2) + f(1)
f(2)
Computing f(1) + f(0)
f(1)
Already computed f(1)
f(0)
Already computed f(0)
f(1)
Already computed f(1)
f(2)
Already computed f(2)
f(3)
Already computed f(3)
f(4)
Already computed f(4)
f(5)
Already computed f(5)
f(6)
Already computed f(6)
f(7)
Already computed f(7)
f(8)
Already computed f(8)
Testing the version with the normal sum, call stack is:
g(10)
Computing g(9) + g(8)
g(9)
Computing g(8) + g(7)
g(8)
Computing g(7) + g(6)
g(7)
Computing g(6) + g(5)
g(6)
Computing g(5) + g(4)
g(5)
Computing g(4) + g(3)
g(4)
Computing g(3) + g(2)
g(3)
Computing g(2) + g(1)
g(2)
Computing g(1) + g(0)
g(1)
Already computed g(1)
g(0)
Already computed g(0)
g(1)
Already computed g(1)
g(2)
Already computed g(2)
g(3)
Already computed g(3)
g(4)
Already computed g(4)
g(5)
Already computed g(5)
g(6)
Already computed g(6)
g(7)
Already computed g(7)
g(8)
Already computed g(8)
所以他们看起来在做完全相同的事情…我的Python版本是3.8.15，你应该试着运行这段代码，看看输出是否也与你的Python版本相同。
在我的Python版本中，我达到了f(333)和g(997)的递归限制
编辑:感谢John Kugelman，我越来越接近答案了，用代码:
import time
import inspect
m = {0:0, 1:1}
def f(n, depth=0):
# fraction part of time
print(f"{' '*depth}f({n})")
if n not in m:
print(f"{' '*depth}Computing f({n-1}) + f({n-2})")
m[n] = sum(f(n - i, depth+1) for i in [1, 2])
else:
print(f"{' '*depth}Already computed f({n})")
print(f"{' '*depth}Returning {m[n]}")
print(f"{' '*depth}Call stack has length {len(inspect.stack())} and is: {[x.function for x in inspect.stack()]}")
return m[n]
print("Testing the version with the iterator, call stack is:")
start = time.time()
f(10)
m = {0:0, 1:1}
def g(n, depth=0):
print(f"{' '*depth}g({n})")
if n not in m:
print(f"{' '*depth}Computing g({n-1}) + g({n-2})")
m[n] = g(n - 1, depth+1) + g(n - 2, depth+1)
else:
print(f"{' '*depth}Already computed g({n})")
print(f"{' '*depth}Returning {m[n]}")
print(f"{' '*depth}Call stack has length {len(inspect.stack())} and is: {[x.function for x in inspect.stack()]}")
return m[n]
print("Testing the version with the normal sum, call stack is:")
g(10)
import sys
print(sys.version)
输出为:
Testing the version with the iterator, call stack is:
f(10)
Computing f(9) + f(8)
f(9)
Computing f(8) + f(7)
f(8)
Computing f(7) + f(6)
f(7)
Computing f(6) + f(5)
f(6)
Computing f(5) + f(4)
f(5)
Computing f(4) + f(3)
f(4)
Computing f(3) + f(2)
f(3)
Computing f(2) + f(1)
f(2)
Computing f(1) + f(0)
f(1)
Already computed f(1)
Returning 1
Call stack has length 20 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
f(0)
Already computed f(0)
Returning 0
Call stack has length 20 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
Returning 1
Call stack has length 18 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
f(1)
Already computed f(1)
Returning 1
Call stack has length 18 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
Returning 2
Call stack has length 16 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
f(2)
Already computed f(2)
Returning 1
Call stack has length 16 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
Returning 3
Call stack has length 14 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
f(3)
Already computed f(3)
Returning 2
Call stack has length 14 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
Returning 5
Call stack has length 12 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
f(4)
Already computed f(4)
Returning 3
Call stack has length 12 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
Returning 8
Call stack has length 10 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
f(5)
Already computed f(5)
Returning 5
Call stack has length 10 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
Returning 13
Call stack has length 8 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
f(6)
Already computed f(6)
Returning 8
Call stack has length 8 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
Returning 21
Call stack has length 6 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
f(7)
Already computed f(7)
Returning 13
Call stack has length 6 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
Returning 34
Call stack has length 4 and is: ['f', '<genexpr>', 'f', '<module>']
f(8)
Already computed f(8)
Returning 21
Call stack has length 4 and is: ['f', '<genexpr>', 'f', '<module>']
Returning 55
Call stack has length 2 and is: ['f', '<module>']
Testing the version with the normal sum, call stack is:
g(10)
Computing g(9) + g(8)
g(9)
Computing g(8) + g(7)
g(8)
Computing g(7) + g(6)
g(7)
Computing g(6) + g(5)
g(6)
Computing g(5) + g(4)
g(5)
Computing g(4) + g(3)
g(4)
Computing g(3) + g(2)
g(3)
Computing g(2) + g(1)
g(2)
Computing g(1) + g(0)
g(1)
Already computed g(1)
Returning 1
Call stack has length 11 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
g(0)
Already computed g(0)
Returning 0
Call stack has length 11 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
Returning 1
Call stack has length 10 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
g(1)
Already computed g(1)
Returning 1
Call stack has length 10 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
Returning 2
Call stack has length 9 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
g(2)
Already computed g(2)
Returning 1
Call stack has length 9 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
Returning 3
Call stack has length 8 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
g(3)
Already computed g(3)
Returning 2
Call stack has length 8 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
Returning 5
Call stack has length 7 and is: ['g', 'g', 'g', 'g', 'g', 'g', '<module>']
g(4)
Already computed g(4)
Returning 3
Call stack has length 7 and is: ['g', 'g', 'g', 'g', 'g', 'g', '<module>']
Returning 8
Call stack has length 6 and is: ['g', 'g', 'g', 'g', 'g', '<module>']
g(5)
Already computed g(5)
Returning 5
Call stack has length 6 and is: ['g', 'g', 'g', 'g', 'g', '<module>']
Returning 13
Call stack has length 5 and is: ['g', 'g', 'g', 'g', '<module>']
g(6)
Already computed g(6)
Returning 8
Call stack has length 5 and is: ['g', 'g', 'g', 'g', '<module>']
Returning 21
Call stack has length 4 and is: ['g', 'g', 'g', '<module>']
g(7)
Already computed g(7)
Returning 13
Call stack has length 4 and is: ['g', 'g', 'g', '<module>']
Returning 34
Call stack has length 3 and is: ['g', 'g', '<module>']
g(8)
Already computed g(8)
Returning 21
Call stack has length 3 and is: ['g', 'g', '<module>']
Returning 55
Call stack has length 2 and is: ['g', '<module>']
3.8.15 (default, Nov 24 2022, 15:19:38)
[GCC 11.2.0]
所以问题是生成器表达式被放在调用堆栈上，占用了实际递归函数可以使用的空间。现在，研究一下为什么生成器表达式会像函数一样被放在堆栈上，这将是一件有趣的事情。
递归深度差异的原因是使用了生成器表达式。
带星号的问题:
为什么下面的语句允许堆栈至少比第一种情况深2倍，这是一个几乎相同的定义:
m={0:0, 1:1}
def f(n):
if n not in m:
m[n] = f(n-2)+f(n-1)
return m[n]
回答这个问题可以帮助你更好地理解记忆。