Return in Recursive Function

python, recursion, return

Solution

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.

Problem

Original source

Related problems

• Why does my recursive function return None?