Return in Recursive Function

Question

I have just started learning python (v3.2.3) and have encountered an odd problem about the return in this function:

def test(x):
    if x > 9 :
        test(x - 10)
    else:
        print('real value',x)
        return x

x = int(input())
y = test(x)
print('this should be real value',y)

When I run it, I get:

45
real value 5
this should be real value None

But I expected:

45
real value 5
this should be real value 5

I tried adding return x outside of if and I got the default input value. Can anyone please explain how return works?

Answer 1

You invoke test(45). This tests whether 45 > 9, which is true, so it invokes test(35) (45 - 10), without returning its result. The same thing happens with test(25) and test(15), until finally test(5) is invoked.

This prints 'real value 5', and then returns 5. But returning a result from a function always returns it to the direct caller of this function. It doesn't jump immediately out through several calls; after all, the caller might want to do something with the returned result before returning something to it's caller. In this case though, only test(5) returns anything at all; all the others call test(x - 10), wait for that to return, ignore whatever it does return, and then (implicitly) return None. Since the outermost invocation test(45) is one of these cases, what you get is None.

Here's an attempt at a visualisation of what happens:

test(45):
| test(35):
| | test(25):
| | | test(15):
| | | | test(5):
| | | | | print('real value',5)
| | | | | return 5 to test(15)
| | | | return None to test(25)
| | | return None to test(35)
| | return None to test(45)
| return None

You didn't call test(5) in the interpreter, test(5) was called from inside another function call. So the return from test(5) goes to that function call. The fact that this is a function calling itself is completely irrelevant. You'd get exactly the same results if your code looked like this:

def test45(x):
    if x > 9 :
        test35(x - 10)
    else:
        print('real value',x)
        return x

def test35(x):
    if x > 9 :
        test25(x - 10)
    else:
        print('real value',x)
        return x

def test25(x):
    if x > 9 :
        test15(x - 10)
    else:
        print('real value',x)
        return x

def test15(x):
    if x > 9 :
        test5(x - 10)
    else:
        print('real value',x)
        return x

def test5(x):
    if x > 9 :
        print 'No more tests :('
    else:
        print('real value',x)
        return x

The test(x) function you call with 'x=45' is same as calling test45(45). I hope you can see why it's obvious that None should be returned when recursion isn't involved. Well, when recursion is involved, nothing changes. The return statement neither knows nor cares whether it's returning from a recursively invoked function, it behaves exactly the same way in either case.

In fact, recursion isn't anything "special" at all; it behaves exactly the same way as ordinary function calls. You receive information from the thing that called you via arguments, and you return information to the thing that called you by returning. If you don't return something (perhaps only in one arm of an if), then None will be returned to your caller, regardless of whether you call any other function in that branch, regardless of what that function might return if you do call something, and regardless of whether the function you call happens to be the same function you're inside.