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/14164.html

    上一篇: 尾递归矢量和

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