After having SICP as my first programming course it always bothered me that Python was so limiting when it came to stack recursion. In the case presented in this article tail recursion was clearly a powerful tool for maintaining abstraction barriers; I'm curious, how do people handle cases like that in Python?
Yes, that's annoying, isn't it? The Python language has an excellent development process IMHO, but, alas, even great processes can produce substandard results now & then. And I think it's clear that leaving TCO out of Python was the wrong decision.
But to address your question: the fact is that OO is rarely taken to this extreme. That's why Cook's article (referenced on this page) had to be written; people just don't think that way.
And even when they do, situations like that in the article are not super common. What we have here is a tree-ish structure in which nodes do computation on their subtrees, and the way in which that computation is done needs to be hidden behind an abstraction barrier. That last is what is forcing the recursion requirement. If it weren't true, then some master function could query all nodes in the tree directly, and an iterative method would work fine.
However, if we are in such a situation, then the fact is that Python just doesn't work as well as some other languages. There is no "way to handle it".
Note, BTW, that TCO is not a complete solution. A function only gets one tail call. If a node needs to query two or more child nodes, then at least one of those calls is not a tail call, and you get stack troubles. The linked page gives an example of just such a situation: the "rebalancing" stuff mentioned in comment #7. See also my comment [#11, id ggchappell]. Guy never responded to it; wish he had.
Thanks for the detailed response. The rebalancing situation is interesting.
Another interesting link I noticed was a discussion on LtU that solves the posed question without using TCO, but it does use types which would again be cumbersome to use in Python.
tail recursion is a particular case of tail call, and I think it's actually the easiest one to do without, by using a looping construct instead of a recursive function. It's often not as beautiful I agree, but this is how you can handle cases where non proper tail recursive calls make your stack explode.
Did you read the whole article though? The whole point of it was that using iteration instead of tail recursion exposes elements of the other classes implementation, which breaks down the abstraction barriers and separation of concerns. The tail recursive approach was able to function while maintaining purity.
Just a miscommunication, then. I was wondering if there was a way of getting around the problems of the iterative approach in Python. After more reading, it seems it could be possible, but messy.
