为什么我的函数在完成时没有再次调用（递归）？

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），以较大者为准。