On 2007-09-14, John Machin <sj******@lexic on.netwrote:
On Sep 14, 10:04 pm, Marc 'BlackJack' Rintsch <bj_...@gmx.net wrote:
>On Fri, 14 Sep 2007 13:40:17 +0200, Gigs_ wrote:
sorry i think that i express wrong. having problem with english
what i mean is how python knows to add all thing at the end of recursion
Because you have written code that tells Python to do so. ;-)
>>def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1]
f([1,2,3])
recursion1 f([2,3]) + [1]
recursion2 f([3]) + [2] or [2, 1]?
recursion3 f([]) + [3] or [3, 2, 1]
Both alternatives in recursion 2 and 3 are wrong. You have to
simply replace the function invocation by its result which
gives:
f([1, 2, 3])
r1 f([2, 3]) + [1]
r2 f([3]) + [2] + [1]
r3 f([]) + [3] + [2] + [1]
r4 [] + [3] + [2] + [1]
And now the calls return:
r3 [3] + [2] + [1]
r2 [3, 2] + [1]
r1 [3, 2, 1]
i dont get all this
>>def f(l):
if l == []:
print l
return []
else:
return f(l[1:]) + l[:1]
>>f([1,2,3])
[]
[3, 2, 1] # how this come here? how python save variables from each
recursion?
There is not just one `l` but one distinct `l` in each call.
I reckon that what the OP wants is a simple explanation of how
function calls use a stack mechanism for arguments and local
variables, and how this allows recursive calls, unlike the good ol'
FORTRAN IV of blessed memory. Perhaps someone could oblige him?
I'd try but it's time for my beauty sleep :-)
<yawn>
Good night all
I may as well stick my neck out again, since I'm already
beautiful. ;)
Another way of understanding recursion is to break it up into
seperate functions, so the spectre of a function calling itself
doesn't appear.
def f(l):
if l == []:
return []
else:
return f(l[1:]) + l[:1]
The function above reverses a list of arbitrary length. To help
understand how it works, I'll write several discreet functions
that sort lists of fixed lengths.
I start with a simple case (though not the simplest case--that
only comes with experience), reversing a two-element list:
def f2(l): # reverse a two-element list
return [l[1], l[0]]
Next build up to the next level, writing a function that can
reverse a three-element list. The key is to be as lazy as
possible. You must figure out a way of taking advantage of the
function that reverses a two-element list. The obvious solution
is to use f2 to reverse the last two elements in our list, and
append the first element in the list to that result:
def f3(l): # reverse a three-element list
return f2(l[1:]) + l[:1]
And so on:
def f4(l):
return f3(l[1:]) + l[:1]
def f5(l):
return f4(l[1:]) + l[:1]
def f6(l):
return f5(l[1:]) + l[:1]
A definite pattern had emerged, and it should be apparent now how
to combine all those functions into one:
def f_(l):
if len(l) == 2:
return [l[1], l[0]]
else:
return f_(l[1:]) + l[:1]
But the function above breaks for lists with less than two items.
>>f_([1])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 2, in f2
IndexError: list index out of range
We can handle that. The reverse of a zero or one-element list is
just itself.
def f_(l):
if len(l) < 2:
return l
elif len(l) == 2:
return [l[1], l[0]]
else:
return f_(l[1:]) + l[:1]
And we've arrived at an OK recursive function that can handle
arbitrary length lists. It's not as simple as it could be,
however. A little intuitive leap, perhaps, will allow you to note
that the case of a two-element list can actually be handled
without a special case:
def f(l):
if len(l) < 2:
return l
else:
return f(l[1:]) + l[:1]
Final note: for reasons of tradition, base cases are almost
always set up as it was in the original function, checking for a
zero-length list, and returning a new empty list, the truly
simplest base case. Another intuitive leap is possibly required
to note that a one-element list is not a special case after all:
it's a reverse of a zero-element list with that one element
appended.
def f(l):
if len(l) == 0:
return []
else:
return f(l[1:]) + l[:1]
Clear as mud?
--
Neil Cerutti
