[Tutor] Re: Help- Simple recursive function to build a list

[Kent Johnson]

actuary77 wrote:
> Kent Johnson wrote:
>>  >>> def rec(n,alist=[]):
>>  ...     _nl=alist[:]
>>  ...     print n,_nl
>>  ...     if n == 0:
>>  ...         print n,_nl
>>  ...         return _nl
>>  ...     else:
>>  ...         _nl=_nl+[n]
>>  ...         return rec(n-1,_nl)
>>  ...
>>  >>> _nl = rec(4)
>> 4 []
>> 3 [4]
>> 2 [4, 3]
>> 1 [4, 3, 2]
>> 0 [4, 3, 2, 1]
>> 0 [4, 3, 2, 1]
>>  >>> print _nl
>> [4, 3, 2, 1]
>>
>> Kent
> 
> Kent, thank you for the answer.
> 
> I just don't understand why.
> 
> I only have one return at the point at the test of the end of the 
> recursion, n == 0.

You have to return a result from each level of recursion. You have
rec(4) <- this returns nothing to its caller
   rec(3, [4]) <- this returns nothing to its caller
     rec(2, [4,3]) <- this returns nothing to its caller
       rec(1, [4,3,2]) <- this returns nothing to its caller
         rec(0, [4,3,2,1]) <- this returns [4,3,2,1] to the call above

By adding the missing 'return', you make all the intermediate invocations return the final result up 
the chain to their caller.

This version shows what is happening:
  >>> def rec(n,alist=[]):
  ...      _nl=alist[:]
  ...      if n == 0:
  ...          print n,_nl
  ...          return _nl
  ...      else:
  ...          _nl=_nl+[n]
  ...          print 'calling rec(', n-1, _nl, ')'
  ...          val = rec(n-1,_nl)
  ...          print 'rec(', n-1, _nl, ') returned', val
  ...          return val
  ...
  >>> rec(4)
calling rec( 3 [4] )
calling rec( 2 [4, 3] )
calling rec( 1 [4, 3, 2] )
calling rec( 0 [4, 3, 2, 1] )
0 [4, 3, 2, 1]
rec( 0 [4, 3, 2, 1] ) returned [4, 3, 2, 1]
rec( 1 [4, 3, 2] ) returned [4, 3, 2, 1]
rec( 2 [4, 3] ) returned [4, 3, 2, 1]
rec( 3 [4] ) returned [4, 3, 2, 1]
[4, 3, 2, 1]


Kent

PS Please send followups to the Tutor list so all may benefit from the discussion.

> 
> I see from the output that the list is being built, up to the point of 
> the one and only return,
> 
> if n == 0:
>     print n,_nl   #  0 [4, 3, 2, 1]
>     return _nl    # None, Why doesn't this return _nl = [4, 3, 2, 1]?
> 
> I can see that the list is being built without the second return.
> And even at the point where the end of the recursion is tested, n == 0,
> the value to be returned, _nl is equal to the desired result?
> The second return is never used!
> The list being built is passed as an argument.
> 
> Scope?
> 
> Why is the second return required?
> 
> Most confused ;(
> 
>