[Tutor] recursion surprise

[Steven D'Aprano]

On 09/06/13 09:12, Jim Mooney wrote:

> Okay, here it is not working a different way, copied exactly, but it
> looks like I do have a return statement, and that it should be
> returning 11, not None. I must be missing something in my
> understanding:
>
> def addone(num):
>      if num > 10:
>          return num
>      num = addone(num + 1)



Follow the code in your head. Suppose you pass 20 as the argument:

1st call to addone:
   num = 20
   "if num > 10" is true, so:
   "return num" returns 20


And we are done. There's no more code to run, because "return" exits the function and there are no more function calls queued up. So far so good. Now, try again, this time with 10 as the argument:

1st call to addone:
   num = 10
   "if num > 10" is false, so the return line is skipped
   num = addone(num + 1)

   At this point, the function pauses, and waits for a result
   from "addone(num + 1)". So we make a recursive call to find
   out what the result of addone(11) is:

   => 2nd call to addone:
        num = 10+1 = 11
        "if num > 10" is false, so:
        "return num" returns 11

   => back to the paused 1st call to addone

   num = addone(num + 1) receives the result 11, so:
   num = 11

   At this point, we hit the end of the function. There's no
   more code to run, and no return statement, so Python
   automatically returns None.

And we're done. addone(10) returns None, not 11 as you hoped.



This might be easier to understand if you drop the recursion, and just use some other calculation:

def simple_addone(num):
     if num > 10:
         return num
     num = num + 1


If you look at simple_addone, it hopefully will be obvious that there are two cases, e.g.:

* simple_addone(20) will return 20

* simple_addone(10) will calculate num = 11, but not do
   anything with it, and then return None when execution
   "drops out the bottom" of the function code.


Here's another example: let's make a second function to perform the addition:

def add(a, b):
     print("adding numbers like a Boss")
     return a+b

def simple_addone(num):
     if num > 10:
         return num
     num = add(num, 1)


The situation is exactly the same. If num starts off > 10, the return statement is reached, and num is returned. But if num starts off <= 10, the return statement is skipped, num is recalculated, but nothing is done with the new result, and None is returned.


Nothing significant changes when you replace the expression num+1 with a call to a function add(num, 1), and likewise nothing significant happens when you replace the call to add() with a recursive call to addone(n+1). The return statement is skipped, you drop out the bottom of the outermost call to addone, and None is returned.


Is this enough information for you to fix it?



-- 
Steven