How can I write a Python decorator to increase stackdepth?

Question

BACKGROUND When playing around, I often write simple recursive functions looking something like: ``` def f(a,b): if a>=0 and b>=0: return min( f(a-1,b) , f(b,a-1) ) # + some cost that depends on a,b else: return 0 ``` (For example, when computing weighted edit distances, or evaluating recursively defined mathematical formulas.) I then use a memoizing decorator to cache the results automatically. PROBLEM When I try something like f(200,10) I get: ``` RuntimeError: maximum recursion depth exceeded ``` This is as expected because the recursive implementation exhausts Python's stack space/ recursion limits. WORKAROUNDS I usually work around this problem by one of: - Increasing recursion limit with sys.setrecursionlimit (only works up to about 1000 depth) - Using a for loop to fill up the cache for smaller values - Changing the function to use a list as a manual stack (via append and pop calls) (in other words, moving from a recursive implementation to an iterative one) - Using an alternat…

Accepted Answer

To get around the recursion limit, you can catch the `RuntimeError` exception to detect when you've run out of stack space, and then return a continuation-ish function that, when called, restarts the recursion at the level where you ran out of space. Call this (and its return value, and so on) until you get a value, then try again from the top. Once you've memoized the lower levels, the higher levels won't run into a recursion limit, so eventually this will work. Put the repeated-calling-until-it-works in a wrapper function. Basically it's a lazy version of your warming-up-the-cache idea.

Here's an example with a simple recursive "add numbers from 1 to n inclusive" function.

```
import functools

def memoize(func):
    cache = {}
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        key = args, tuple(sorted(kwargs.items()))
        if key in cache:
            return cache[key]
        else:
            result = func(*args, **kwargs)
            if not callable(result):
                cache[key] = result
            return result
    return wrapper

@memoize
def _addup(n):
    if n < 2:
        return n
    else:
        try:
            result = _addup(n - 1)
        except RuntimeError:
            return lambda: _addup(n)
        else:
            return result if callable(result) else result + n

def addup(n):
    result = _addup(n)
    while callable(result):
        while callable(result):
            result = result()
        result = _addup(n)
    return result

assert addup(5000) == sum(xrange(5001))
```

Rather than returning the lambda function all the way back up the call chain, we can raise an exception to short-circuit that, which both improves performance and simplifies the code:

```
# memoize function as above, or you can probably use functools.lru_cache

class UnwindStack(Exception):
    pass

@memoize
def _addup(n):
    if n < 2:
        return n
    else:
        try:
            return _addup(n - 1) + n
        except RuntimeError:
            raise UnwindStack(lambda: _addup(n))

def _try(func, *args, **kwargs):
    try:
        return func(*args, **kwargs)
    except UnwindStack as e:
        return e[0]

def addup(n):
    result = _try(_addup, n)
    while callable(result):
        while callable(result):
            result = _try(result)
        result = _try(_addup, n)
    return result
```

This remains pretty inelegant, though, and still has a fair amount of overhead, and I can't imagine how you'd make a decorator out it. Python isn't really suited to this kind of thing, I guess.

How can I write a Python decorator to increase stackdepth?

Solution

Problem

Related problems