recursion

[Marc 'BlackJack' Rintsch]

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.

Ciao,
	Marc 'BlackJack' Rintsch