你能用这些看似等价的函数来解释 Python 中递归深度的差异吗？

Question

你能用这些看似等价的函数来解释 Python 中递归深度的差异吗？

我注意到在我的机器上，以下内容达到了 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]

Run Code Online (Sandbox Code Playgroud)

而这个版本达到 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]

Run Code Online (Sandbox Code Playgroud)

谁能解释一下“幕后”发生了什么来解释这种差异？

更准确地说，如果能够理解为什么此示例中的因子为 3，并能够导出它以使用更多项进行求和，那就太好了。

Answer 1

wim*_*wim 18

TL;DR： sum是一个额外的函数调用，它求和的生成器表达式也是使用嵌套函数作用域实现的（文档）

\n

\n
...理解是在单独的隐式嵌套范围中执行的。这确保目标列表中分配给的名称不\xe2\x80\x99t \xe2\x80\x9cleak\xe2\x80\x9d 进入封闭范围。
\n

\n

因此，第二种方法在递归期间使用两个额外的堆栈帧以及递归调用本身，这解释了这里的因子 3。

\n

请注意，默认递归限制为 1000，因此您实际上应该看到第一种情况的堆栈溢出恰好为 1000，第二种情况的堆栈溢出为 334（在 Python 3.10 或更低版本上）。要在这里获得 2960 和 988，您可能有：

\n

进口了一些叫做sys.setrecursionlimit(3000), 和
已经在某个地方花费了一些堆栈帧。

\n

例如，在 IDE 或精心设计的交互式 REPL 中运行此代码可能会完成上述两项操作。

\n

有趣的最新进展：

\n

有PEP 709 \xe2\x80\x93 内联推导式，其全部目的是从推导式中删除此隐藏函数。生成器表达式当前未内联在 PEP 的参考实现中，尽管将来可能会考虑。

\n

CPython 3.11 已经进行了一些优化，以减少此代码中的函数调用次数，从而改变了堆栈溢出的点。它将发生在 CPython 3.11 中的 501 而不是 334。更改日志中描述了原因：What\xe2\x80\x99s Python 3.11 中的新增功能：内联 Python 函数调用。

\n

Answer 2

Car*_*orc 2

这是一个令人着迷的行为，我没有找到问题的根源，但我仍然想分享一些我编写的日志代码，这些代码可能会帮助其他人找到问题：

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)

Run Code Online (Sandbox Code Playgroud)

输出是：

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)

Run Code Online (Sandbox Code Playgroud)

所以他们看起来在做完全相同的事情...我的 Python 版本是 3.8.15，您应该尝试运行此代码以查看输出是否也与您的 Python 版本相同。

f(333)在我的 Python 版本中，我达到了和的递归限制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)

Run Code Online (Sandbox Code Playgroud)

输出是：

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]

Run Code Online (Sandbox Code Playgroud)

所以问题是生成器表达式被放在调用堆栈上，占用了实际递归函数可以使用的空间。现在研究一下为什么生成器表达式像函数一样被放入堆栈中会很有趣。

归档时间：	2 年，8 月前
查看次数：	1901 次
最近记录：	2 年，8 月前