瞭解遞歸概念使用兩個遞歸

Question

我想解決合併排序，我迷路在遞歸概念。爲了讓自己更好理解，我畫了一個小例子。

隨着n= 2下面的程序我得到的答案爲0,1,2我完全瞭解使用堆棧，並通過puts n完成遞歸後一個返回堆棧一個值的概念。

def one(n) 
    if n < 0 
    return 
    end 
    one(n-1) 
    puts n 
end 

但是，當我試圖用另一種遞歸像下面我完全失去了，爲什麼又是怎樣回答0,0,1,0,0,1,2。任何人都可以解釋它嗎？

def one(n) 
    if n < 0 
    return 
    end 
    one(n-1) 
    one(n-1) 
    puts n 
end 

請詳細說明兩個遞歸如何協同工作。

Answer 1

這是你的第二次遞歸的圖形表示。這些行表示操作的順序;遞歸級別列：

n = 2 
return if n < 0 
one(1) ->  n=1 
       return if n < 0 
       one(0) ->  n=0 
            return if n < 0 
            one(-1) ->  n=-1 
                return if n < 0 
                <- 

            one(-1) ->  n=-1 
                return if n < 0 
                <- 
            puts 0 
            <- 

       one(0) ->  n=0 
            return if n < 0 
            one(-1) ->  n=-1 
                return if n < 0 
                <- 

            one(-1) ->  n=-1 
                return if n < 0 
                <- 
            puts 0 
            <- 
       puts 1 
       <- 

    one(1) ->  n=1 
       << same as above, resulting in `puts 0`, `puts 0`, `puts 1` >> 
       <- 
    puts 2 

想象每個遞歸級別（列），就好像它是一個單獨的方法。它執行一些操作，然後調用另一種方法。在這種情況下，它自稱，但你不應該這樣想;把它想成是調用某種方法。最終該方法返回，可能帶有一個值（但不在這裏），並且該方法以常規方式繼續到下一個語句（行）。最終它返回到調用它的方法。這恰好是同樣的方法，但是再一次，將其視爲一種方法。

通過constrast，這是與你的第一個遞歸發生的事情：

n = 2 
return if n < 0 
one(1) ->  n=1 
       return if n < 0 
       one(0) ->  n=0 
            return if n < 0 
            one(-1) ->  n=-1 
                return if n < 0 
                <- 
            puts 0 
            <- 
       puts 1 
       <- 
puts 2 

Answer 2

one(n)呼叫one(n-1)兩次，然後調用puts n，所以它看起來像：

one(2) -> one(1) -> one(0) -> one(-1) 
          \> one(-1) 
          \> puts 0 
       \> one(0) -> one(-1) 
          \> one(-1) 
          \> puts 0 
       \> puts 1 
     \> one(1) -> one(0) -> one(-1) 
          \> one(-1) 
          \> puts 0 
       \> one(0) -> one(-1) 
          \> one(-1) 
          \> puts 0 
       \> puts 1 
     \> puts 2 

上述圖像中的函數調用是這樣的：one(2)呼叫one(1)，它調用one(0)，然後調用one(-1)，這one(-1)返回，一（0）呼叫第二個one(-1)，第二個one(-1)返回，one(0)呼叫puts 0，然後one(0)返回，返回第二個one(0)等