recursion

Steve Holden steve at holdenweb.com
Fri Sep 14 14:47:18 CEST 2007

```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
>
>  >>> 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]
>
>
> 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?
>
>
> sorry again for first post
>
I think the thing you are missing is that the recursive call f(l[1:]) in
the return statement causes the current call to be suspended until the
recursive call is complete. The new call has its own value for l, which
is the caller's l[1:]. Each new call creates a completely new namespace.

A less complicated function might make it a little more obvious.

def factorial(n):
print "n =", n
if n=0:
return 1
else:
return n * factorial(n-1)

Try running that with a few different arguments to show you how the
recursion works.

regards
Steve
--
Steve Holden        +1 571 484 6266   +1 800 494 3119
Holden Web LLC/Ltd           http://www.holdenweb.com
Skype: holdenweb      http://del.icio.us/steve.holden

Sorry, the dog ate my .sigline

```