递归的工作原理

Question

static void sort(int array[])
{
    //int array[]={20,40,30,60,70,80,50,90};
    if(array.length==1)
        return;

    int mid=array.length / 2;
    int part1[]=new int[mid];
    int part2[]=new int[array.length-mid];

    for(int i=0; i<array.length; i++)
    {
        if(i<mid)
        {
            part1[i]=array[i];
        }
        else
        {
            part2[i-mid]=array[i];
        }
    }

    sort(part1);
    sort(part2);

    merge(part1,part2,array);
    //for(int x=0; x<part1.length; x++)
        //System.out.print(part1[x]+" ");

    //for(int x=0; x<part2.length; x++)
        //System.out.print(part2[x]+" ");

}

我知道递归是调用它自己的方法（函数）。我在这段代码中困惑为什么该程序停止，当 sort() 方法执行并调用自己 sort(part1)method 然后 sort(part1) 一次又一次执行以及 sort(part2) 和 merge(part1,part2,array ) 被执行，为什么这段代码不是无限的以及程序如何停止。抱歉，我是 Java 新手

Answer 1

每个递归调用都在一个只有父调用一半大的段上工作：

int mid=array.length / 2;

当子段长度达到 1 时，递归处于“基本情况”并且该方法返回：

if(array.length==1)
    return;

我认为这实际上是Quicksort 的一个实现。该算法属于称为Divide and Conquer的算法家族，因为它们的工作原理是将问题递归地划分为越来越小的部分，解决更小的问题，最后组合更小的解决方案以获得完整的结果。

既然您知道该算法的名称，如果您想更好地了解它的工作原理，我建议您更详细地研究该算法。维基百科文章甚至有一个很好的动画来帮助你形象化算法是如何工作的。

请注意，发布的代码将导致空数组的无限递归。Quicksort 避免这种情况的常用方法是使用length检查基本情况？1而不是length = 1。