On 2007-09-14, John Machin <[EMAIL PROTECTED]> wrote:
> On Sep 14, 10:04 pm, Marc 'BlackJack' Rintsch <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
