Return in Recursive Function

by

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.

More Related Contents:

  1. Why does my recursive function return None?
  2. Recursive code returns None [duplicate]
  3. What is the maximum recursion depth in Python, and how to increase it?
  4. Recursive function returning none in Python [duplicate]
  5. return, return None, and no return at all?
  6. How can I return two values from a function in Python?
  7. Python recursion with list returns None [duplicate]
  8. Basics of recursion in Python
  9. Python: Maximum recursion depth exceeded
  10. What’s the best way to return multiple values from a function? [duplicate]
  11. recursive iteration through nested json for specific key in python
  12. Recursion and return statements
  13. python recursion return None type
  14. Using self.xxxx as a default parameter – Python
  15. Recursive function returning none? [duplicate]
  16. Setting property causes maximum recursion depth exceeded
  17. How to find common elements in list of lists?
  18. return eats exception
  19. python recursive vectorization with timeseries
  20. Change values in dict of nested dicts using items in a list?
  21. In Python, if I return inside a “with” block, will the file still close?
  22. Python: using a recursive algorithm as a generator
  23. How can a recursive regexp be implemented in python?
  24. python recursive function that prints from 0 to n?
  25. Where to use the return statement with a loop?
  26. Python: maximum recursion depth exceeded while calling a Python object
  27. How do I reverse a list using recursion in Python?
  28. Finding all maze solutions with Python
  29. getattr and setattr on nested subobjects / chained properties?
  30. How to constuct a column of data frame recursively with pandas-python?

Leave a Comment