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

    上一篇: 尾递归矢量和

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