Python 中的尾递归优化装饰器

Question

我最近一直在学习Scala，所以我用Python写了一些递归。

我发现 Python 中没有尾递归优化。

然后我找到了一个魔术（？）装饰器，它似乎可以优化尾递归。

它解决了RuntimeError: maximum recursion depth exceeded.

但我不明白这段代码是如何工作的以及为什么。

有人可以解释一下这段代码中的魔力吗？

法典：

# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is 
# its own grandparent, and catching such 
# exceptions to recall the stack.
import sys
class TailRecurseException:
  def __init__(self, args, kwargs):
    self.args = args
    self.kwargs = kwargs
def tail_call_optimized(g):
  """
  This function decorates a function with tail call
  optimization. It does this by throwing an exception
  if it is its own grandparent, and catching such
  exceptions to fake the tail call optimization.
  This function fails if the decorated
  function recurses in a non-tail context.
  """
  def func(*args, **kwargs):
    f = sys._getframe()
    if f.f_back and f.f_back.f_back 
        and f.f_back.f_back.f_code == f.f_code:
      raise TailRecurseException(args, kwargs)
    else:
      while 1:
        try:
          return g(*args, **kwargs)
        except TailRecurseException, e:
          args = e.args
          kwargs = e.kwargs
  func.__doc__ = g.__doc__
  return func
@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.

Answer 1

如果没有尾部调用优化，您的堆栈如下所示：

factorial(10000)
factorial(9999)
factorial(9998)
factorial(9997)
factorial(9996)
...

并增长，直到您拨打sys.getrecursionlimit()电话（然后是 Kaboom）。

使用尾部调用优化：

factorial(10000,1)
factorial(9999,10000) <-- f.f_back.f_back.f_code = f.f_code? nope
factorial(9998,99990000) <-- f.f_back.f_back.f_code = f.f_code? yes, raise excn.

异常使装饰器转到其while循环的下一次迭代。