Tail-Recursion Optimization Decorator in Python

Question

I have been learning Scala recently, so I wrote some recursion in Python.

And I found there is no tail-recursion optimization in Python.

Then I found a magic(?) decorator that seems to optimize the tail-recursion.

It solved the RuntimeError: maximum recursion depth exceeded.

But I don't understand how and why this code works.

Can somebody explain the magic power inside this code?

code:

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

Which part don't you understand? Do you already know what tail call optimization is and how it works - and you want to understand decorators? Or stacks? Or exceptions? As it stands, this question is way too broad to be answered meaningfully here. — Tim Pietzcker
– Tim Pietzcker, Commented Dec 11, 2014 at 8:01
Thank you for your comment. It's my fault didn't ask the question clearly and haven't read the comment in code carefully. — VoidBzY
– VoidBzY, Commented Dec 11, 2014 at 8:27
If you care about tail recursion in Python, you should have a look at the tco module; see the presentation: baruchel.github.io/python/2015/11/07/… — Thomas Baruchel
– Thomas Baruchel, Commented Nov 7, 2015 at 6:33

dnozay · Accepted Answer · 2014-12-11 08:15:01Z

3

without tail call optimization your stack looks like this:

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

and grows until you reach sys.getrecursionlimit() calls (then kaboom).

with tail call optimization:

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.

and the exception makes the decorator go to the next iteration of its while loop.

answered Dec 11, 2014 at 8:15

dnozay

24.4k6 gold badges85 silver badges105 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Tail-Recursion Optimization Decorator in Python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related