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




More information about the Python-list mailing list