def recursive_example(n, d=1):
    if n <= 1:
        return d
    else:
        return recursive_example(n - 1, d + 1)

try:
    recursive_example(10000)
except Exception as ex:
    print(ex)

maximum recursion depth exceeded in comparison

Of course, catching excess recursion neatly (as Python did above) is a feature. It is one way to stop possible run-away recursions.

However, if we want one particular function to exceed this limit (especially for tail calls, which should require no memory overhead!): we need to set up a framework similar to “Tail call recursion in Python”.

First we build a “thunk” to represent the evaluation of a function with all arguments specified, but that hasn’t happened yet. We implement pending calculations with the class data_algebra.pending_eval.PendingFunctionEvaluation (source here). The extra bit is: we have PendingFunctionEvaluation extend Exception, so we can use raise to jump out of our current function context.

Then, when we have what would normally be a “tail call” of the form “return f(x)“, we instead write “raise PendingFunctionEvaluation(f, x)“. The idea is: we end our current function by raising the exception, and the exception itself has the instructions for the desired next step or continuation of the calculation. An outer wrapper then iteratively evaluates any PendingFunctionEvaluations encountered. Thus any tail recursion is replaced by iteration, and we have eliminated the stack and memory use of the tail calls. It should also be possible to use a return-style notation with the PendingFunctionEvaluation wrapper, but we feel the raise notation more clearly documents intent.

An example is given here:

import data_algebra.pending_eval as pe

def recursive_example_ex(n, d=1):
    if n <= 1:
        return d
    else:
        # eliminate tail-call by using exception
        # instead of return recursive_example_ex(n-1, d+1)
        raise pe.PendingFunctionEvaluation(
            recursive_example_ex, n - 1, d + 1)

pe.eval_using_exceptions(recursive_example_ex, 100000)

100000

Nota bene: the raise will throw-through any intermediate functions, so any non-tail calls (direct or indirect) to these throwing functions would have to go use the eval_using_exceptions() guard! After working some examples, we have settled that the original return-based mechanism is better. The exceptions are too hard to manage and don’t add much. For our adaptation of the return-based example, please see here.

We can also specialize the method for method-calls as we show below. The pattern we are using is a simple one: methods ending in an underbar raise exceptions in place of tail-calls (and only call the underbar versions of methods), and an outer method without an underbar performs the exception handling.

class C:

    def f_(self, n, d=1):
        if n <= 1:
            return d
        else:
            # Eliminate tail-call by using an exception.
            # instead of: return self.f_(n-1, d+1), use:
            raise pe.PendingFunctionEvaluation(
                self.f_, n - 1, d + 1)

    def f(self, n, d=1):
        return pe.eval_using_exceptions(self.f_, n=n, d=d)

o = C()
o.f(100000)

100000