Another Coder Confused by Recursion

This question already has an answer here:

What is tail recursion? 23 answers

---

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.

We receive the return value of slowAdd(m, n-1) .

We add 1 to the return value

We return the sum from #2.

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)))

链接地址: http://www.djcxy.com/p/80464.html

上一篇: 如何通过所有可能性增加一个Java String？

下一篇: 另一个编码器被递归混淆