[Tutor] recursion and trampolines

Danny Yoo dyoo at hkn.eecs.berkeley.edu
Thu Aug 26 05:36:27 CEST 2004

> >Are there anything else?
> A few things to note:
> - I'm not too fond of the recursive structure of SpcfName. This
> structure has cropped up a few times on this list recently - maybe we
> have a few converts from LISP.

[advanced; skip if you haven't seen Scheme/Lisp code or recursion.]

We also have to bring up that Python doesn't implement "tail call
elimination". Python's recursion depth is limited, so certain
constructions that work in Scheme/Lisp don't work so well in Python, at
least, not without some adjustments.

As a concrete example, a Python function like:

def broken_fact(n, k = 1):
    if n == 0:
        return k
    return broken_fact(n-1, n * k)

is broken for any "n" that's greater than the system's recursion limit.

>>> sys.getrecursionlimit()
>>> broken_fact(2)
>>> broken_fact(3)
>>> broken_fact(1000)
>>> broken_fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 4, in broken_fact
  File "<stdin>", line 4, in broken_fact

[... a LOT of lines cut.  *grin*]

  File "<stdin>", line 4, in broken_fact
  File "<stdin>", line 4, in broken_fact
RuntimeError: maximum recursion depth exceeded

One place we might see this kind of RuntimeError, in practice, is with
nongreedy regular expressions.  Python's implementation of nongreedy
regexes uses a recursive algorithm that dies badly on certain inputs.

>>> s = 'Begin ' + 1000*'a very long string ' + 'end'
>>> re.match('Begin (\w| )*? end', s).end()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "/usr/lib/python2.3/sre.py", line 132, in match
    return _compile(pattern, flags).match(string)
RuntimeError: maximum recursion limit exceeded

(this example is taken from: http://www.python.org/doc/lib/node109.html)

So although this thing is mostly esoteric, it can effect us.

That being said, there is a technique to work around the lack of tail
recursion, called "trampolined style".


It allows us to write recursive programs that avoids growing the call
stack, even in languages that don't natively support tail call

Here's a concrete example of a trampolined version of that factorial
function, using the trampolining technique:

def trampolined_fact(n, k=1):
    if n == 0:
        return land(k)
    return bounce(trampolined_fact, n-1, k*n)

def fact(n):
    """Returns the factorial of n."""
    return trampoline(trampolined_fact, n)

def trampoline(function, *args):
    """Bounces a function over and over, until we "land" off the
    bouncer = bounce(function, *args)
    while True:
        bouncer = bouncer[1](*bouncer[2])
        if bouncer[0] == 'land':
            return bouncer[1]

def bounce(function, *args):
    """Bounce back onto the trampoline, with an upcoming function call."""
    return ["bounce", function, args]

def land(value):
    """Jump off the trampoline, and land with a value."""
    return ["land", value]

And now we're in business:

>>> fact(1000)
23155861103697680135730421616874760... [text cut]

Anyway, I thought this was really cool.  *grin* Hope this helps!

More information about the Tutor mailing list