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 ;(
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
