C语言 为什么我的基本情况被(错误地)立即触发?

Question

我正在尝试在 C 语言中实现合并排序算法。在递归数组拆分函数中，尽管有 return 语句，但我的基本情况是无限发生的，并且永远不会调用合并函数。这是我的代码：

#include <stdio.h>
const int MAX = 1000;
int getArray(int unsorted[MAX], int upperBound)
{
int i;
for(i = 0; i <= upperBound; ++i)
{
printf("Now enter integer number %d: ", i + 1);
scanf("%d", &unsorted[i]);
while((getchar()) != 'n');
}   
printf("n");
return 0;
}
int merge(int unsorted[MAX], int sorted[1000], int lowerLeft, int lowerRight)
{
if(lowerLeft == lowerRight)
return 0;
int j = lowerRight;
for(int i = lowerLeft; i < lowerRight; ++i)
{
if(unsorted[i] <= unsorted[j])
{
sorted[i] = unsorted[i];
++j;
}
else
{
sorted[i] = unsorted[j];
++j;
}
}
return 1;
}
int split(int unsorted[MAX], int sorted[1000], int lowerBound, int upperBound)
{
printf("%d is the lBound and %d is the uBoundn", lowerBound, upperBound);
if(lowerBound == upperBound)
{
printf("nBase case triggered.");
getchar();
return 0;
}
int middle = upperBound/2;
split(unsorted, sorted, 0, middle);
split(unsorted, sorted, middle + 1, upperBound);    
merge(unsorted, sorted, lowerBound, middle);
return 1;
}
int main()
{
int unsorted[MAX];
int sorted[MAX];
int lowerBound = 0;
int upperBound;
printf("First enter the number of integers you wish to sort: ");
scanf("%d", &upperBound);
while((getchar()) != 'n');
printf("n");
upperBound = upperBound - 1;
getArray(unsorted, upperBound);
split(unsorted, sorted, lowerBound, upperBound);
printf("n");
for(int c = 0; c < upperBound; ++c)
{
printf("%d, ", sorted[c]);
}
return 0;
}

为什么到达基本情况后不调用合并函数？对不起，如果我没有方便地表达这个问题，希望有人能在这里帮助我，谢谢。

Answer 1

您的基本情况被触发，因为这就是递归算法的工作方式。你一遍又一遍地调用split()，下限和上限之间的差距越来越低，所以最终你的基本情况会被触发。这应该是一件好事，因为触发基本情况可以让您知道您的输入"数组"(单例(已排序并且可以合并。

它被"立即"触发的原因是它必须： split(( 被不断调用，直到满足基本情况，所以你会看到的第一个 print 语句是基本情况。