Throw the cat among the pigeons

[Cecil Westerhof]

Op Tuesday 5 May 2015 17:47 CEST schreef Paul Moore:

> On Sunday, 3 May 2015 16:23:59 UTC+1, Cecil Westerhof  wrote:
>>> By the way: I think that even if the recursion does not go further
>>> as 500, it is still a good idea to use tail recursion. Why use
>>> stack space when it is not necessary?
>>
>> I pushed the example to GitHub:
>> https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py
>
> You already know this, as your code shows, but tail call recursion
> elimination is only possible when you have a *direct* tail call (one
> with the result of the tail call returned immediately to the
> caller). Even the standard trivial factorial example doesn't have a
> direct tail call, without rewriting to use an accumulator variable.
> Which is a non-intuitive transformation to anyone who's not familiar
> with recursive functional languages and their idioms.
>
> If you're rewriting your recursive function *anyway*, it's not that
> much harder in many (most?) cases to rewrite it iteratively.
>
> An example of a function that naturally uses direct tail call
> recursion, but which doesn't have a simple iterative rewrite, would
> be more compelling. Not particularly compelling (to me, anyway) even
> so, but still better than factorial or fibonnaci examples.

Well, I did not write many tail recursive functions. But what surprised
me was that for large values the ‘tail recursive’ version was more
efficient as the iterative version. And that was with myself
implementing the tail recursion. I expect the code to be more
efficient when the compiler implements the tail recursion.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof