通過堆疊自省優化尾遞迴

預設情況下，Python 的遞迴堆疊不能超過 1000 幀。這可以通過設定更快的 sys.setrecursionlimit(15000) 來改變，但是這種方法消耗更多的記憶體。相反，我們也可以使用堆疊內省來解決 Tail Recursion 問題。

#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's 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 it's 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 裝飾器來呼叫我們的函式。以下是使用上述裝飾器的一些常見遞迴示例：

析因示例：

@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.