你能用那些看似等效的代码来解释 Python 中深度递归的这种差异吗？

问题描述 投票：0回答：4

我注意到在我的机器上，以下达到 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 并且能够推导它以用于更多项的求和，那将是非常好的。

python recursion limit
4个回答
7
投票

TL;DR: 

sum
是一个额外的函数调用，它求和的生成器表达式也是用嵌套函数作用域实现的 (docs)

...理解是在一个单独的隐式嵌套范围内执行的。这确保了目标列表中分配给的名称不会“泄漏”到封闭范围中。

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

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

  • 进口了一个叫做
    sys.setrecursionlimit(3000)
    的东西，和
  • 已经在某处花费了一些栈帧。

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

最近有趣的发展：

有 PEP 709 – 内联理解，它是关于从理解中删除这个隐藏函数。生成器表达式目前没有内联在 PEP 的参考实现中，尽管将来可能会考虑。

CPython 3.11 已经有一些优化来减少这段代码中的函数调用次数，从而改变堆栈溢出的点。在 CPython 3.11 中它将发生在 501 而不是 334。原因在 Python 3.11 的新增功能：内联 Python 函数调用.

的变更日志中进行了描述
3
投票

我也会在这里添加我的调试。运行一些测试后，我发现 

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

看来生成器确实是在向栈中添加一个函数调用，而且每个生成器表达式在调用栈上算作两个函数。这解释了您原始问题中的比率。不知道为什么会这样，我欢迎任何可能的解释！

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)

输出为：

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]

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

1
投票

递归深度不同的原因是使用了生成器表达式。

带星的问题：

与第一种情况相比，为什么以下允许堆栈至少深 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]

回答这个问题可以帮助你更好地理解记忆。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.