瞭解雙遞歸

Question

如果在函數中只有一個遞歸調用，我可以很容易地理解遞歸。但是，當我在同一個函數中看到兩個或多個遞歸調用時，我真的感到困惑。例如：

int MaximumElement(int array[], int index, int n) 
    { 
     int maxval1, maxval2; 
     if (n==1) return array[index]; 
     maxval1 = MaximumElement(array, index, n/2); 
     maxval2 = MaximumElement(array, index+(n/2), n-(n/2)); 
     if (maxval1 > maxval2) 
      return maxval1; 
     else 
      return maxval2; 
    } 

我明白一件事情，在每次遞歸調用期間，n都減半。我只是不明白下一個遞歸調用的工作原理。它變得混亂和我的理解，直到這一點崩潰，我放棄了。我會非常感激，如果有人可以請用一個整潔的例子手動說明。我已經做了編程，並打印輸出。但是，我不明白這項工作背後的計算方式。這是我的理解，直到這裏的一切變得不了了之點：

INT一個[] = {} 1,2,10,15,16,4,8

初始呼叫：MaximumElement（一，0， 7）

的功能開始： 第一次調用：MaximumElement（A，0，7/2） ñ現在變爲7/2 = 3

第二個呼叫：MaximumElement（2,0,3/2） n現在變成3/2 = 1

基本con第二次遞歸調用以索引0開始，並且n =索引+ n/2 = 0 + 1/2 = 0這是第二次遞歸調用從索引0開始並且n =索引+ n/2 = 0 + 1/2 = 0 ？當我打印這些值時，第二次調用時程序顯示3爲n的值。

我已經編程了很多，但我真的有這個噩夢。非常感謝有人能爲我打破這個！

這是上面的僞代碼，但請參閱下面的Java代碼我寫的（它可能使你更容易，如果你想運行它）：

 public int MAXIMUMELEMENT(int a[], int i, int n) 
     { 
     int max1, max2; 

     System.out.println("1: " + i + " 2: " + n); 

     if(n == 1) 
     { 
      System.out.println("Returning " + a[i]); 
     return a[i]; 
     } 



     max1 = MAXIMUMELEMENT(a, i, n/2); 

     System.out.println("Index: "+i+" "+" Variable: "+max1+" n value: "+n); 


      max2 = MAXIMUMELEMENT(a, i + (n/2), n - (n/2)); 

     System.out.println("Index2: " + i + " " + "Variable2: " + max2); 


     if(max1 > max2) 
     { 
      System.out.println("Returning.... " + max1);  
       return max1; 
     } 
     else 
     { 
     System.out.println("Returning.... " + max2);  
     return max2; 
     } 
} 

Answer 1

這聽起來像你已經明白了基本情況，知道遞歸是如何工作的，所以關鍵是瞭解你的具體的例子是要注意，給定初始陣列

a = [1,2,10,15,16,4,8] 

您是，在「頂級」計算兩兩件事：

maxval1 = MaximumElement(array, 0, 3); 
maxval2 = MaximumElement(array, 3, 4); 

它說

• 使maxval1從該範圍中的陣列的最大值從大小的索引0開始3
• 使maxval2從該範圍中的陣列的最大值從大小爲4的指數3

所以

• maxval1的確是10
• maxval2的確將是16

和您的答案將是16

約遞歸的好處是，你不必擔心跟蹤的東西太廣泛。如果你信任你的基本情況和你基本情況的方式，那麼理解一個層次就足夠了。

我覺得你被困在你說「所有地獄都打破了鬆散」的地方，因爲第二個遞歸調用以0的起始索引開始。它從索引3開始。（也就是說，假設你的第二次遞歸調用是計算的maxVal2）。

這裏有一點你的計算如何工作的一個縮寫跟蹤。我冒昧地將您的函數重命名爲m，並假設maxVal1和maxVal2的計算更「功能性」一點。

a = [1,2,10,15,16,4,8] 

m(a, 0, 7) 
= m(m(a, 0, 3), m(a, 3, 4)) 
= m(m(m(a, 0, 1), m(a, 1, 2)), m(a, 3, 4)) 
= m(m(a[0], m(a, 1, 2)), m(a, 3, 4)) 
= m(m(1, m(a, 1, 2)), m(a, 3, 4)) 
= m(m(1, m(m(a, 1, 1), m(a, 2, 1)), m(a, 3, 4)) 
= m(m(1, m(a[1], a[2])), m(a, 3, 4)) 
= m(m(1, m(2, 10)), m(a, 3, 4)) 
= m(m(1, 10), m(a, 3, 4)) 
= m(10, m(a, 3, 4)) 
= … 
= 16 

Answer 2

在我看來，你已經對遞歸調用的運行順序感到困惑。請記住，第二次調用（maxval2）在第一次調用（maxval1）結束之前不會被調用。 maxval1調用本身有兩個遞歸調用等等。因此，如果沒有完成所有這些內部遞歸調用，程序將無法到達maxval2行。

嘗試調試而不是運行代碼（例如在Eclipse中）並逐步移動以查看它是如何實際執行每次遞歸調用的。

Answer 3

我不確定我能否很好地解釋它，但我會用斐波那契來解釋它。 計算斐波那契數的遞歸方法是：

public static int getFib(int n) { 
    if(n <= 2) return 1; 
    return getFib(n-1)+getFib(n-2); 
} 

實際發生的代碼是什麼，它會明顯下降的方法調用，直到它到達第一回報。 所以getFib(n-1)將繼續調用，直到n <= 2然後它將回到方法棧，並且因爲它現在具有該getFib（n-1）的值，它將調用getFib（n-2）。 所以說，我們最初的通話是4，什麼情況是：

getFib(4) //Initial call 
    getFib(4-1=3) //Left hand recursive call level 1 
    getFib(3-1=2) //Left hand recursive call level 2 
     return 1 //This would be level 3 
    getFib(3-2=1) //Right hand recursive call level 2 
     return 1 //level 3 
    getFib(4-2=2) //Right hand recursive call level 1 
    return 1 

不知道如果讓任何意義，這種形象可能它想象一下： Recursive fibonacci tree http://www.fortystones.com/wp-content/uploads/2011/08/fibonacci-recursion-tree.png

上面的代碼基本上會做先深入（先讓左邊的孩子）穿過那棵樹。