recursive function return value problems

[Steven D'Aprano]

On Wed, 28 Dec 2005 15:25:30 -0800, randomtalk wrote:

> hi, i have the following recursive function (simplified to demonstrate
> the problem):
> 
>>>> def reTest(bool):
> ... 	result = []
> ... 	if not bool:
> ... 		reTest(True)
> ... 	else:
> ... 		print "YAHHH"
> ... 		result = ["should be the only thing returned"]
> ... 	print "printing result: "
> ... 	print result
> ... 	return result
> ...
>>>> reTest(False)
> YAHHH
> printing result:
> ['should be the only thing returned']
> printing result:
> []
> []
> 
> I don't understand why results are returned twice? is there something
> special i missed about recursive functions?

No. What happens when you do this?

py> def test():
...     print "spam"
...     return "Spam"
... 
py> test()
spam
'Spam'

I've deliberately spelt one in all lower case, and the other with an upper
case S, so it is easier to see the difference.

When you just call a function from the interactive interpreter without
assigning to a name, Python automatically prints the return value. In your
test above, you call reTest(False) without assigning the result to
anything, so after reTest prints all the various things it has to print,
the interpreter also prints the return result.

If you get that, you can stop reading. Otherwise, here is a more
careful analysis.

When you call reTest(False), it creates a local variable 'result' to the
empty list, then calls reTest(True).

reTest(True) then creates a new local variable 'result', sets it to the
empty list, prints "YAHHH", sets result to a string inside a list. It
prints "printing result", then prints ["should be the only thing..."], and
finally returns that string inside a list.

Control now returns to the *first* call to reTest(False). It accepts that
string inside list, *but throws the result away*. You didn't do anything
with the result! You probably want to change that line to
result=reTest(True).

Because this is inside a function, the result of reTest(True) doesn't get
printed, so you don't see it. (Python only automatically prints results of
things you type at the interactive prompt.)

Execution now continues past the if...else... block. It prints "printing
result", then it prints the value of 'result' which is still equal to the
empty list. Finally it returns the empty list, and the Python interpreter
prints the empty list as a convenience for you.

Calling a recursive function is no different from calling any other
function: you want to assign the result to something.

def factorial(n):
    """Returns n! = 1*2*3*...*(n-1)*n for non-negative int n"""
    # this is inefficient code, but it does demonstrate recursion well
    if n == 0:
        result = 1
    else:
        result = n*factorial(n-1)
    return result



-- 
Steven.