Combining memoization and tail call optimization

Question

I recently learned about a powerful way to use decorators to memoize recursive functions.
"Hey that's neat, let's play with it!"

class memoize:
    """Speeds up a recursive function"""
    def __init__(self, function):
        self.function = function
        self.memoized = {}

    def __call__(self, *args):
        try:
            return self.memoized[args]
        except KeyError:
            self.memoized[args] = self.function(*args)
            return self.memoized[args]
#fibmemo
@memoize
def fibm(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibm(n - 1, next, current+next)

Which timeit shows this indeed speeds up the algorithm:

fibmemo     0.000868436280412
fibnorm     0.0244713692225

"Wow, that could be really useful! I wonder how far I can push it?"
I found when I start using inputs higher than 140, I quickly ran into RuntimeError: maximum recursion depth exceeded. "Ahh shucks.."

After a little searching I found a hack that appears to solve the problem.
"This looks neat, too! Let's play with it"

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

#fibtail
@tail_call_optimized
def fibt(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibt(n - 1, next, current+next)

Ok, so I have a way to speed up my fibonacci function using memoize. I have a way to push the recursion limits. I can't figure out how to do both.

#fibboth
@memoize
@tail_call_optimized
def fibb(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibb(n - 1, next, current+next)

fibboth     0.00103717311766 
fibtail     0.274269805675
fibmemo     0.000844891605448
fibnorm     0.0242854266612

I've tried combining the decorators which LOOKS like it works for inputs below 140, but the moment I go beyond that, RuntimeError: maximum recursion depth exceeded occurs. It's almost like the @tail_call_optimized fails. "What the...?"

---

QUESTION:

1. Is there a way to combine these decorators? If so, how?
2. Why when combined does it appear that the decorators are working for smaller inputs?

Answer 1

@NathanDavis nailed it in his answer - you should accept it. tail_call_optimized() is nasty code, relying on two things:

1. That it knows exactly what the call stack looks like; and,
2. That it matters not one whit if it destroys part of the call stack.

If you apply it all on its own, to a truly tail-recursive function, those are fine. But combine it with another decorator, and #1 is no longer true. You can try to "repair" that, like this (for example):

def tail_call_optimized(g):
    def func(*args, **kwargs):
        f = sys._getframe()
        code = f.f_code
        fcount = 0
        while f:
            if f.f_code is code:
                fcount += 1
                if fcount > 1:
                    raise TailRecurseException(args, kwargs)
            f = f.f_back
        while 1:
            try:
                return g(*args, **kwargs)
            except TailRecurseException, e:
                args = e.args
                kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

Now it searches back the call stack any number of frames to "find itself" again, and that indeed gets rid of the recursion-limit exception. But, as Nathan implied, when it raises TailRecurseException that also gets rid of in-progress calls to the memoization decorator. In the end, after calling (say) fibb(5000), only argument 5000 will be in the memo.

You could complicate it yet again, to restitch the call stack to throw away only the in-progress calls to the tail_call_optimized decorator, and then the memo would work correctly again. But - surprise! ;-) - then the call stack would still contain in-progress calls to all the levels of the memo decorator, and you'd hit the maximum recursion limit again. Since the memo function itself does not end with a call (i.e., it's never correct to throw away a stack frame corresponding to a memo function call), there's no simple way to worm around that.

Answer 2

There are two issues here: the first is that, as @badcook points out, the memoize decorator technically transforms your function into a non-tail-recursive function. However, the tail_call_optimized decorator doesn't care about that.

The second issue, and the reason it doesn't work, is that the memoize decorator adds an additional frame to the stack every time fibb is called. So instead of being its own grand-parent, it is more like its own great-grand-parent. You could fix the check, but be aware that the memoize decorator will be effectively bypassed.

So the morale of the story is that tail call optimization and memoization do not mix.

Of course, for this particular problem, there is a way to solve the problem in a logarithmic number of steps anyway (see SICP exercise 1.19 at http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4 for more details), making the issue pretty moot in this case. But that's not what this question is about.