Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Chris Angelico]

On Mon, Jul 13, 2015 at 11:46 PM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
> On Mon, Jul 13, 2015 at 6:34 AM, Chris Angelico <rosuav at gmail.com> wrote:
>> On Mon, Jul 13, 2015 at 10:00 PM, Antoon Pardon
>> <antoon.pardon at rece.vub.ac.be> wrote:
>>> On 07/13/2015 01:28 PM, Chris Angelico wrote:
>>>> Why is it worth writing your code recursively, only to have it be
>>>> implemented iteratively?
>>>
>>> Because sometimes, it is easier to think about the problem recursively.
>>
>> Can you give me an example that (a) makes a lot more sense recursively
>> than iteratively, and (b) involves just one tail call?
>
> Why does (b) matter? If the function has more than one tail call, it
> doesn't matter which one you hit -- either way it's a tail call and
> the stack frame is no longer needed.

Oops. I meant "involves just one point of recursion". When you
traverse a tree, only one can be a tail call, because after the other,
you still have more processing to do. Most problems that I've found to
work recursively and not iteratively have involved multiple branches -
consider a simplistic solution to the Eight Queens problem that places
a queen, then calls itself to place another queen:

def eightqueens(positions=()):
    for i in range(8):
        if i not in positions:
            # TODO: check for the diagonals
            result = eightqueens(positions + (i,))
            if result: return result
    return None

While it can do the classic "call self, return result", it has to
conditionally _not_ do that and keep on going. While this algorithm
can be implemented iteratively, it's a reasonable show-case for
recursion; but not for tail recursion, because one call to
eightqueens() might result in more than one chained call, so I don't
think there's any way for TCO to kick in here.

What I'm asking for is an example of something that can have the tail
calls optimized away, and yet still looks cleaner - preferably,
*significantly* cleaner - in its recursive form than in its
corresponding iterative form. Considering that an iterative function
can maintain state that isn't in the parameters, I'm dubious that such
a thing exists outside of the deranged minds of functional
programmers. (Very much deranged. If you consider that a recursive
factorial just uses addition and subtraction, while an iterative one
can start with "for i in range(n):", you will agree that my
terminology is strictly correct. So there.)

ChrisA