为什么我的函数在完成时没有再次调用（递归）？
我目前完成我的代码。但由于某种原因，我的递归调用在最后没有被触发？有没有某种我偶然想到的特殊代码？为什么我的函数在完成时没有再次调用（递归）？
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);
}
你的算法有点搞砸了。例如，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);
}
与输出：
[email protected]:~/src/sandbox$ ./max
12
[email protected]:~/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);
}
输出：
[email protected]:~/src/sandbox$ ./max
Greatest value is 12 at index 4
[email protected]:~/src/sandbox$
只有到max第一个电话 - 一个位于main - 它的返回值实际上分配到任何东西。递归调用返回的值立即丢失;他们所做的工作对最终结果毫无意义。您需要将递归调用的结果分配给max至greatest。
请记住，每次递归调用都会打开一个新范围，每个范围都有其自己的greatest变量版本。每次递归调用中的赋值只修改它们的变量版本，而不是来自封闭范围的版本;这意味着第一次调用的版本在取值为arr[0]后从未设置为任何值;这是当最外层呼叫恢复时，其值返回到main的版本，无论递归调用在两者之间完成的工作如何。
你也有一个无关的错误，这是你递归到另一个呼叫到max（和调用内分配给greatest）检查您是否已经达到了数组的结束，这将溢出超越前数组的末尾，并覆盖最后的结果（无论发现在那里）（正如Paul指出的那样，在与当前值进行比较之前，您还指定greatest，所以比较实际上没有意义）。您需要移动检查内的所有内容，以确保不会发生。
我似乎无法包裹我的头，以递归调用的结果为最大到最大。 – BeginnerC 2014-10-20 02:43:39
当我做得最好= arr [开始]时，我不是已经这么做吗？对不起，我现在只是很困惑...... – BeginnerC 2014-10-20 02:45:18
@BeginnerC字面意思是递归调用应该写成'最大=最大（...'，就像它出现在'main'中一样。这听起来像你不是完全掌握变量范围和递归的作用每一个嵌套的函数调用都有自己的所有局部变量的副本 - 想象它们是“最大{0}”，“最大{1}”等。分配给“最大的{1}”对于最大的{0}'没有任何效果，它在递归调用之前处于相同的状态。 – Leushenko 2014-10-20 02:47:50
我相信递归调用是被触发，但没有做你想做的。你将arr [start]初始化为最大值（在这种情况下为8），并且从不分配任何其他值，所以当然你的函数返回8.相反，如果start> = end，你的函数应该返回arr [start] ，否则应返回arr [start]或max（arr，start + 1，end），以较大者为准。
你需要复制 - 和 - 将*精确*代码粘贴到问题中。通过重新输入它，你已经引入了一个错字（'printf'的'pintf'）。我们无法猜测您的问题中的代码与您询问的代码之间可能存在哪些其他差异。 – 2014-10-20 14:54:17