On 5/5/2015 12:18 PM, Cecil Westerhof wrote:
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
An 'indirect tail call' would not be a tail call.
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.
For count functions, the main change between tail recursion and while
iteration is replacing 'if' with 'while' and converting the tail call to
assignment. (One may have to reverse the if-else first to put the tail
call in the if branch.)
from math import factorial as fac
print(fac(0), fac(1), fac(2), fac(6))
def fac_rt(n, i=2, res=1):
if i <= n:
return fac_rt(n, i+1, res*i)
else:
return res
def fac_iw(n):
i = 2
res = 1
while i <= n:
i, res = i+1, res*i
return res
for i in (0, 1, 2, 6):
print(fac(i) == fac_rt(i) == fac_iw(i))
>>>
1 1 2 720
True
True
True
True
For collection functions that process each item once, 'for item in
collection: ...' is nearly always easier to write in the first place.
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.
Simple, easily converted functions like the above, with one recursive
call in one branch of an if-else, are the most common. Something with
multiple mutually exclusive tail calls, like the following
def f_rt1(*args):
if nonbase1:
return f(*revised-args1)
elif base_condition:
return base(args)
else:
return f(*revised-args2)
must be converted to if-else with all tail calls in the if branch.
def f_rt2(*args):
if not base_condition:
if nonbase1:
return f(*revised-args1)
else:
return f(*revised-args2)
else:
return base(args)
Conversion would then be simple. The complication is that the
'base_condition' in the original version might not really be the base
condition due to a dependence on nonbase1 being false. This is a
generic problem with reordering if-elif statements.
For non-linear (branching) recursion, in which multiple recursive calls
may be made for one function call, the last recursive call may be a tail
call. An example is in-place quick sort. Eliminating just the tail
call may not be simple, but it also does not eliminate the possibility
of blowing the call stack. To do that, one must eliminate all recursive
calls by adding explicit stacks.
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.
In your first thread, what you mislabelled 'tail recursive version' was
an iterative while loop version while the 'iterative version' was an
iterative for loop version. In this thread, you just posted timings
without code. I will not believe your claim until I see one file that I
can run myself with an actual tail recursive function, as above, that
beats the equivalent while or for loop version.
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
