[Tutor] recursion and trampolines

[Danny Yoo]

> >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()
1000
>>> broken_fact(2)
2
>>> broken_fact(3)
6
>>> 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".

    http://www.cs.indiana.edu/hyplan/sganz/publications/icfp99/paper.pdf

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


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
    trampoline."""
    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)
4023872600770937735437024339230039857193748642107146325
4379991042993851239862902059204420848696940480047998861
0197196058631666872994808558901323829669944590997424504
0870737599188236277271887325197795059509952761208749754
6249704360141827809464649629105639388743788648733711918
1045825783647849977012476632889835955735432513185323958
4630755574091142624174743493475534286465766116677973966
6882029120737914385371958824980812686783837455973174613
6085379534524221586593201928090878297308431392844403281
23155861103697680135730421616874760... [text cut]
###


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