Jaguar已经很好地阐述了这个概念,Paul也提供了正确和详细的解释。
为了补充这一点,我想分享一个简单的C代码,让您了解代码如何执行。以下是与Jaguar使用相同输入的代码:
#include<stdio.h>
int findMaxHelper(int A[], int left, int right){
int max1,max2;
int static tabcount;
int loop;
for(loop = 0 ; loop <tabcount;loop++) printf("\t");
tabcount++;
printf(" Entering: findMaxHelper(A, left = %d ,right = %d)\n\n",left,right);
if (left == right - 1){
for(loop = 0 ; loop <tabcount;loop++) printf("\t");
printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d)| returning %d\n\n",left,right , A[left]);
tabcount--;
return A[left];
}
else
{
max1 = findMaxHelper(A, left, (right + left) / 2);
max2 = findMaxHelper(A, (right + left) / 2, right);
if (max1 > max2){
for(loop = 0 ; loop <tabcount;loop++) printf("\t");
printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d) | returning max1=%d\n\n",left,right,max1);
tabcount--;
return max1;
}
else {
for(loop = 0 ; loop <tabcount;loop++) printf("\t");
printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d)| returning max2=%d\n\n",left,right,max2);
tabcount--;
return max2;
}
}
}
int main (){
int A[] = { 34,3,47,91,32,0 };
int Ans =findMaxHelper(A,0,7);
printf( "And The Answer Is = %d \n",Ans);
}
您可以将代码复制粘贴到您的Linux机器上...也许在每个printf后面加上sleep(5),看看递归是如何实际工作的!...
希望这能有所帮助...
我也会在此分享我的系统输出:
Entering: findMaxHelper(A, left = 0 ,right = 7)
Entering: findMaxHelper(A, left = 0 ,right = 3)
Entering: findMaxHelper(A, left = 0 ,right = 1)
Leaving: findMaxHelper(A, left = 0 ,right = 1)| returning 34
Entering: findMaxHelper(A, left = 1 ,right = 3)
Entering: findMaxHelper(A, left = 1 ,right = 2)
Leaving: findMaxHelper(A, left = 1 ,right = 2)| returning 3
Entering: findMaxHelper(A, left = 2 ,right = 3)
Leaving: findMaxHelper(A, left = 2 ,right = 3)| returning 47
Leaving: findMaxHelper(A, left = 1 ,right = 3)| returning max2=47
Leaving: findMaxHelper(A, left = 0 ,right = 3)| returning max2=47
Entering: findMaxHelper(A, left = 3 ,right = 7)
Entering: findMaxHelper(A, left = 3 ,right = 5)
Entering: findMaxHelper(A, left = 3 ,right = 4)
Leaving: findMaxHelper(A, left = 3 ,right = 4)| returning 91
Entering: findMaxHelper(A, left = 4 ,right = 5)
Leaving: findMaxHelper(A, left = 4 ,right = 5)| returning 32
Leaving: findMaxHelper(A, left = 3 ,right = 5) | returning max1=91
Entering: findMaxHelper(A, left = 5 ,right = 7)
Entering: findMaxHelper(A, left = 5 ,right = 6)
Leaving: findMaxHelper(A, left = 5 ,right = 6)| returning 0
Entering: findMaxHelper(A, left = 6 ,right = 7)
Leaving: findMaxHelper(A, left = 6 ,right = 7)| returning 0
Leaving: findMaxHelper(A, left = 5 ,right = 7)| returning max2=0
Leaving: findMaxHelper(A, left = 3 ,right = 7) | returning max1=91
Leaving: findMaxHelper(A, left = 0 ,right = 7)| returning max2=91
And The Answer Is = 91