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?

It is exactly the same as with a non-recursive call: if you want to propagate the return value from the function you called, you have to do that yourself, with the `return` keyword. Calling a function produces its return value, but it's up to you to do something with that return value, whether the called function is recursive or not. — Karl Knechtel, Jul 06 '12 at 06:23

score 95 · Answer 1 · edited Apr 18 '16 at 21:59

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.

score 30 · Answer 2 · answered Jul 06 '12 at 05:13

30

The return is indented so it only executes in the else branch. If the first branch is taken, the function implicitly returns None.

You need to change this to

return test(x-10)

answered Jul 06 '12 at 05:13

Antimony

37,781
10
100
107

so does this mean that i need to have return even on the false unexecuted if condition ? – Alex Key Jul 06 '12 at 06:22
1

@AlexKey: Yes. Since `y` is assigned the value from the first function call only. This is not something that is unique to Python. The only part that is unique to Python is that functions implicitly return `None` when there is no return statement. – Joel Cornett Jul 06 '12 at 07:08
I found the explanation in the answer above useful for understanding but it didn't provide any direction or advice on how to actually resolve the problem. Thanks for keeping it simple! – theYnot Apr 22 '23 at 09:49

score 5 · Answer 3 · answered Jul 06 '12 at 05:13

5

You forgot to return the value when x > 9. Without the return value, the function will "return" None.

answered Jul 06 '12 at 05:13

nhahtdh

55,989
15
126
162

so in summary i need to put return on both the condition is it ? – Alex Key Jul 06 '12 at 06:19
@AlexKey: In the code above, yes, you will return the value of evaluating `test(x - 10)` – nhahtdh Jul 06 '12 at 07:51

Return in Recursive Function

3 Answers3

Linked