分而治之遞歸

我只是想了解遞歸在這個例子中是如何工作的，並且如果有人能夠爲我分解這個，我將不勝感激。我有以下的算法基本上返回最大數組中的元素：分而治之遞歸

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; 
    }

我無法理解的遞歸調用在這裏是如何工作的。第二次調用時，第一次遞歸調用是否總是被執行？我真的很感激，如果有人可以請向我解釋這一點。非常感謝！嵌入式

來源

2013-09-23 acc_so

這是我假設的C++嗎？ –

沒有特定的編程語言。我只是想了解這個方法/函數/僞代碼背後的概念。我有一個Java背景。 –

在Java中，你可能不會使用'int n'參數（但你可以）。 –

代碼註釋：

// the names index and n are misleading, it would be better if we named it: 
    // startIndex and rangeToCheck 
int MaximumElement(int array[], int startIndex, int rangeToCheck) 
{ 
    int maxval1, maxval2; 

    // when the range to check is only one cell - return it as the maximum 
    // that's the base-case of the recursion 
    if (rangeToCheck==1) return array[startIndex]; 
    // "divide" by checking the range between the index and the first "half" of the range 
    System.out.println("index = "+startIndex+"; rangeToCheck/2 = " + rangeToCheck/2); 
    maxval1 = MaximumElement(array, startIndex, rangeToCheck/2); 
    // check the second "half" of the range 
    System.out.println("index = "+startIndex+"; rangeToCheck-(rangeToCheck/2 = " + (rangeToCheck-(rangeToCheck/2))); 
    maxval2 = MaximumElement(array, startIndex+(rangeToCheck/2), rangeToCheck-(rangeToCheck/2)); 

    // and now "Conquer" - compare the 2 "local maximums" that we got from the last step 
    // and return the bigger one 
    if (maxval1 > maxval2) 
     return maxval1; 
    else 
     return maxval2; 
}

使用示例：

int[] arr = {5,3,4,8,7,2}; 
int big = MaximumElement(arr,0,arr.length-1); 
System.out.println("big = " + big);

輸出：

index = 0; rangeToCheck/2 = 2 
index = 0; rangeToCheck/2 = 1 
index = 0; rangeToCheck-(rangeToCheck/2 = 1 
index = 0; rangeToCheck-(rangeToCheck/2 = 3 
index = 2; rangeToCheck/2 = 1 
index = 2; rangeToCheck-(rangeToCheck/2 = 2 
index = 3; rangeToCheck/2 = 1 
index = 3; rangeToCheck-(rangeToCheck/2 = 1 
big = 8

來源

2013-09-23 02:03:22 alfasin

我瞭解基本情況。我試圖理解遞歸調用，但我不明白它是如何工作的。例如：你有一個大小爲6（2,4,1,3,5,6）的數組。遞歸調用如何工作？第一個調用是maxva1l = MaximumElement（array，0，6/2），第二個調用變爲（maxval1 = MaximumElement（array，0，3/2）？ –

@acc_so你必須更具體一些... – alfasin

我很抱歉！我試圖問的是，該片段如何處理值爲{2,4,1,3,5,6}的大小爲6的數組？感謝很多!!那就是：不是輸出看起來像，但遞歸調用的每一步是如何工作的也許，一個大小爲4的數組可能很容易解釋 –

這到底是怎麼發生的是均爲遞歸調用正在一個接一個地進行。第一個搜索有數組並返回最大值，第二個搜索另一半並返回最大值。然後比較兩個最大值，並返回更大的最大值。

來源

2013-09-23 02:04:19

非常感謝回覆！ –

是的。你猜到的是對的。在兩個遞歸調用MaximumElement(array, index, n/2)和MaximumElement(array, index+(n/2), n-(n/2))中，重複執行第一個調用，直到調用數組的單個元素。然後將這兩個元素進行比較，並返回最大值。然後繼續這個比較過程直到返回最大的元素。

來源

2013-09-23 02:05:37 Deepu

這就是我最初的理解，但是在所有比較都是ma之前，不會終止程序德？ –

否。返回將僅終止一個特定的函數調用執行。其他函數調用將被執行。 – Deepu

請稍微詳細一點！： - ）你能用一個簡單的例子來解釋遞歸嗎？就像有4個值的數組？ –

分而治之遞歸

回答

相關問題