To do tail recursion with Python2

末尾再歸にて 最適裡に 實行するには class を 作りて @ より 始まる　meta programming を おこなふと いふ。 (ref: http://code.activestate.com/recipes/496691/)

tail_recursive.py

class tail_recursive (object):

  def __init__(self, func):
    self.func = func
    self.firstcall = True
    self.CONTINUE = object()

  def __call__(self, *arguments, **keywords):
    if self.firstcall:
      func = self.func
      CONTINUE = self.CONTINUE
      self.firstcall = False
      try:
        while True:
          result = func(*arguments, **keywords)
          if result is CONTINUE: # update arguments
            arguments, keywords = self.argskwd
          else: # last call
            return result
      finally:
        self.firstcall = True
    else: # return the arguments of the tail call
      self.argskwd = arguments, keywords
      return self.CONTINUE

これを @tail_recursive として 用ゐる。 たとへば 次:

@tail_recursive
def sum(n, acc=0):
  if n == 0:
    return acc
  else:
    return sum(n - 1, acc + n)

@tail_recursive 有らざるも 動き得。 されども その stack すぐに overflow す。