Suppose I wanted to add two numbers but I can only increment and decrement by 1. I can solve this problem a number of ways including using recursion. When I add m and n I can use the following Python definition:
def slowAdd(m, n):
if n == 0:
return m
else:
return 1 + slowAdd(m, n-1)
This is really confusing to me. Can someone explain how the final return call operates? How does Python interpret the value of a defined function when adding it to 1?
Well, let's look at a super simple function.
def super_simple_function():
return 0
What happens when I do x = super_simple_function()?
>>> x = super_simple_function()
>>> x
0
That's because the function's return value is zero. So there's a function object, which gives (returns) you a value when called.
Let's look at your recursive function, line by line. Imagine we passed in 2 and 3 as our arguments, like so: slowAdd(2, 3).
Line 1: def slowAdd(m, n)
This means that the first argument equals to m and second, n. Therefore, in our case, m = 2 and n = 3.
Line 2: if n == 0
This is the condition that triggers when n equals to 0. Well, right now n = 3 so this condition is ignored.
Line 3: return m
Because n doesn't equal to 0, this line is ignored for now; we'll come back to it.
Line 4 & 5: else: return 1 + slowAdd(m, n-1)
There are three things happening here.
slowAdd(m, n-1).This function is called recursive because of #1. As you can imagine, this function will keep calling itself until n == 0, at which point it returns m instead of 1 + slowAdd(m, n-1). And because we are decrementing n by 1 in every recursion, we know for sure that n will eventually equal to 0.
So this is basically what the function is doing when we pass (2, 3) as arguments:
1st recursion: return 1 + slowAdd(2, 2)
2nd recursion: return 1 + slowAdd(2, 1)
3rd recursion: return 1 + slowAdd(2,0)
4th recursion: return 2 # n is finally 0!
Which add up to 2 + 1 + 1 + 1 = 5.
Think about it as substituting the "slowAdd(m, n-1)" with the correct return expression (either "m" if n=0, otherwise subsitute "1 + slowAdd(m, n-1)").
Example:
slowAdd(5,3)
1 + slowAdd(5, 3-1)
1 + (1 + slowAdd(5, 2-1))
1 + (1 + (1 + slowAdd(5, 1-1)))
1 + (1 + (1 + 5))) // n=0
During the return call for n!=0, the function calls itself again adding 1 to the n-1th value. I would explain this better by an illustration. Following is what is happening with your called function:(slowAdd(1,3):)
slowAdd(1,3)
returns 1+slowAdd(1,2)
returns 1+slowAdd(1,1)
returns 1+slowAdd(1,0)
returns 0
So what is happening is:
1+3
=1+(1+2)
=1+(1+(1+1))
=1+(1+(1+(1+0)))
when we execute a program there is what we call stack of execution
when a function (A) call another function (B). the programme save the context of the function A in the stack of execution so that it can continue the execution of the function (A) when finishing function (B).
the context is all the local variable of the function and the remaining instructions.
lets suppose that we call the function like this slowAdd(1,9) before calling slowAdd(1,9) the programme will save the context so it will save the current value of n=1 and the current value of m=9 and the last instruction that is 1+slowAdd(0,9) it will then call slowAdd(0,9) slowAdd(0,9) will return 9 and the programme will get back to the first call to the function. it will restore the context and it will substitute the call with the returning value. 1+slowAdd(0,9) will be 1+9
You can add a print statement inside the loop and you can see what's going on, also the line if n == 0: can be written as if not n:
def slowAdd(m, n):
if not n: return m
else:
print('1 + ({}, {})'.format(m, n))
return 1 + slowAdd(m, n-1)
print(slowAdd(5,5))
1 + (5, 5)
1 + (5, 4)
1 + (5, 3)
1 + (5, 2)
1 + (5, 1)
10
