On 7/17/2015 4:55 PM, Marko Rauhamaa wrote:
Terry Reedy <tjre...@udel.edu>:
On 7/16/2015 3:45 PM, Marko Rauhamaa wrote:
Nobody seemed to notice that I just posted a fairly typical tail call
function:
Because non-recursive tail calls are completely normal.
I don't know how recursion makes a difference
There are two extremely important differences:
1. Direct recursion calls the function that contains the call. This is
what allows replacement of tail recursion with a loop within the same
function.
2. Almost all problems with stack overflow are due to recursion, whether
at the tail or within the body of a code block. Such problems are nearly
always with linear recursion (one recursive call per call until the base
case). Problems with branching recursion (multiple recursive calls per
call) are rare except for very deep trees and graphs.
but that one did happen to be recursive.
Not directly, as needed for loop conversion.
class X: # omitted from original but needed below
def setvalue(self, keyseq, value, offset=0):
...
child.setvalue(keyseq, value, offset + 1)
child.setvalue is a new callable bound method object, call it 'bm', that
is different from the setvalue function. This tail call is not a tail
recursive call. The standard conversion of adding a while loop and
replacing the tail call with the assignment in the call, in this case
'offset = offset+1' will not work.
It could easily have been replaced with a while loop
Given the equality stated below, then yes.
child.setvalue(*args) == bm(*args) calls (in 3.x)
bm.__func__(bm.__self__, *args)
If type(child) == type(self) == X, then bm.func == X.setvalue
and the indirect call is the same as
X.setvalue(child, keyseq, value, offset + 1)
making the bound method call indirectly recursive.
If we replace the bound method call in setvalue with the call to
setvalue itself, then we have a tail recursive call and can do the
standard replacement to get:
class X
def setvalue(self, keyseq, value, offset=0):
while True:
...
# child.setvalue(keyseq, value, offset + 1)
offset += 1
self = child
If children are not always instances of type(self), as when a tree has
separate Node and Leaf classes, then recursive calls to Node instances
must be separated from non-recursive Leaf calls before replacing the
recursive calls.
Having a good reason to rebind the first parameter within methods, as
above, is a good reason to not hide it (as some have proposed).
but there were good aesthetic reasons to leave it recursive.
Once one learns that looping and recursive calls are two ways of doing
the same thing -- repeatedly executing a block of code with altered
inputs, then the aesthetic reasons are purely aesthetic.
I personally would probably initially write and test setvalue with
recursion. If I were releasing it for others to use in production code
(where aesthetics no longer break ties between equivalent correct
implementations), I would do the conversion to avoid possible stack
overflows. For cases like this, where only some parameters are rebound,
I might leave the original tail call in a comment as documentation, as I
did above.
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
