爲什麼我的函數在完成時沒有再次調用（遞歸）？

Question

我目前完成我的代碼。但由於某種原因，我的遞歸調用在最後沒有被觸發？有沒有某種我偶然想到的特殊代碼？

int max(int arr[], int start, int end) {  
     int greatest = arr[start]; 
     if(start < end) 
     { 

     if(greatest<arr[start]) 
     { 
      greatest = arr[start]; 
     } 
     start++; 
     max(arr, start, end); // Doesn't seem to be triggering since it only returns 8 
     } 
     return greatest; 
}  

int main() 
{ 
    int greatest; 
    int arr[10] = {8,1,2,3,4,5,6,7,8,9}; 
    int start = 0; 
    int end = 10; 
    greatest=max(arr, start, end); 

    pintf("%d\n", greatest); 

} 

Answer 1

你的算法有點搞砸了。例如，greatest<arr[start]永遠不會是真的，因爲您只需設置greatest = arr[start]。這裏有一個評價工作的算法：

#include <stdio.h> 

int max(int arr[], int start, int end) 
{ 
    if (start >= end) { 

     /* Shouldn't get here, but return 0 if we do */ 

     return 0; 
    } 
    else if (end - start == 1) { 

     /* Only one element, so it's the maximum by definiton */ 

     return arr[start]; 
    } 
    else { 

     /* Find the maximum of the rest of the list... */ 

     int greatest = max(arr, start + 1, end); 

     /* ...and return the greater of it, and the first element */ 

     return arr[start] > greatest ? arr[start] : greatest; 
    } 
} 

int main(void) 
{ 
    int arr[] = { 8, 1, 2, 3, 12, 5, 6, 7, 8, 9 }; 
    int start = 0; 
    int end = 10; 
    int greatest = max(arr, start, end); 

    printf("%d\n", greatest); 
} 

與輸出：

paul@thoth:~/src/sandbox$ ./max 
12 
paul@thoth:~/src/sandbox$ 

讓我們通過它與一個簡單的列表，{1，5,3}。每個縮進級別表示您的遞歸函數調用之一。每次我們看到max()，我們都會上升到一個水平 - 每當我們看到return時，我們就會回到一個水平。

In main(), int greatest = max(list, 0, 3) 

    In call 1: (end - start == 1) is false 
    In call 1: int greatest = max(list, 1, 3) 

     In call 2: (end - start == 1) is false 
     In call 2: int greatest = max(list, 2, 3) 

      In call 3: (end - start == 1) is true 
      In call 3: return arr[2], which is 3 

     Back in call 2: greatest now equals 3 
     Back in call 2: arr[1] == 5, which is > 3, so return arr[1], which is 5 

    Back in call 1: greatest now equals 5 
    Back in call 1: arr[0] == 1, which is not > 5, so return greatest, which is 5 

Back in main(), greatest now equals 5 

記住，每次你看到int greatest時間，這是一個的正在創建不同變量。他們都有相同的名字，但由於他們都在不同的範圍內，他們仍然是不同的。例如，呼叫2中的int greatest與呼叫1中的int greatest完全分開，正如呼叫1中的int greatest與main()中的int greatest完全分開。

編輯：從評論，如果你想最大值的指數爲好，這會做到這一點：

#include <stdio.h> 

int max_index(int arr[], int start, int end) 
{ 
    if (start >= end) { 
     return 0; 
    } 
    else if (end - start == 1) { 
     return start; 
    } 
    else { 
     int greatest = max_index(arr, start + 1, end); 
     return arr[start] > arr[greatest] ? start : greatest; 
    } 
} 

int max(int arr[], int start, int end) 
{ 
    if (start >= end) { 

     /* Shouldn't get here, but return 0 if we do */ 

     return 0; 
    } 
    else if (end - start == 1) { 

     /* Only one element, so it's the maximum by definiton */ 

     return arr[start]; 
    } 
    else { 

     /* Find the maximum of the rest of the list... */ 

     int greatest = max(arr, start + 1, end); 

     /* ...and return the greater of it, and the first element */ 

     return arr[start] > greatest ? arr[start] : greatest; 
    } 
} 

int main(void) 
{ 
    int arr[] = { 8, 1, 2, 3, 12, 5, 6, 7, 8, 9 }; 
    int start = 0; 
    int end = 10; 
    int greatest = max(arr, start, end); 
    int index = max_index(arr, start, end); 

    printf("Greatest value is %d at index %d\n", greatest, index); 
} 

輸出：

paul@thoth:~/src/sandbox$ ./max 
Greatest value is 12 at index 4 
paul@thoth:~/src/sandbox$ 

Answer 2

只有到max第一個電話 - 一個位於main - 它的返回值實際上分配到任何東西。遞歸調用返回的值立即丟失;他們所做的工作對最終結果毫無意義。您需要將遞歸調用的結果分配給max至greatest。

請記住，每次遞歸調用都會打開一個新範圍，每個範圍都有其自己的greatest變量版本。每次遞歸調用中的賦值只修改它們的變量版本，而不是來自封閉範圍的版本;這意味着第一次調用的版本在取值爲arr[0]後從未設置爲任何值;這是當最外層呼叫恢復時，其值返回到main的版本，無論遞歸調用在兩者之間完成的工作如何。

你也有一個無關的錯誤，這是你遞歸到另一個呼叫到max（和調用內分配給greatest）檢查您是否已經達到了數組的結束，這將溢出超越前數組的末尾，並覆蓋最後的結果（無論發現在那裏）（正如Paul指出的那樣，在與當前值進行比較之前，您還指定greatest，所以比較實際上沒有意義）。您需要移動檢查內的所有內容，以確保不會發生。

Answer 3

我相信遞歸調用是被觸發，但沒有做你想做的。你將arr [start]初始化爲最大值（在這種情況下爲8），並且從不分配任何其他值，所以當然你的函數返回8.相反，如果start> = end，你的函數應該返回arr [start] ，否則應返回arr [start]或max（arr，start + 1，end），以較大者爲準。