python - Python 中的尾递归优化装饰器

Question

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

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

然后我found a magic(?) decorator这似乎优化了尾递归。

它解决了运行时错误:超出最大递归深度。

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

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

代码:

# 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 循环的下一个迭代。