有人可以解释一下递归的工作原理吗。我试图弄清楚在每次递归调用时分别以低,中,高的方式写下来。但是我似乎以某种方式犯了一个错误。有人可以告诉我这些步骤。我也没有了解值返回到的位置

if(leftmax>rightmax){
    return leftmax;
}
else
    return rightmax;


这是代码:

public class Maximum{
    public static  int max(int[] a,int low,int high){
        int mid,leftmax,rightmax;
        if(low==high)
            return a[low];
        else{
            mid=(low+high)/2;
            leftmax=max(a,low,mid);
            rightmax=max(a,mid+1,high);
            if(leftmax>rightmax){
                return leftmax;}
            else
                return rightmax;
        }
    }

    public static void main (String args[]){
        int[] a={32,8,12};
        System.out.println(max(a,0,2));
    }
}

最佳答案

因此,这似乎是著名的分而治之算法,用于查找元素(在这种情况下为最大元素)。

该方法从以下输入开始:

max(int[] a, int low, int hight)

a[] = { 32, 8, 12 }; //The target array. You want to find the maximum element in it.
low = 0; //The index of the array where you will start searching
high = 2; //The index of the array where you will stop searching


因此,基本上,低和高定义了一个“范围”,您将搜索该范围内的最大元素,如果要搜索整个数组,则将范围指定为索引0和最大可能索引,即数组的长度-1(请记住,索引从零开始,因此您需要减去偏移量)

方法中的第一个条件检查是否给定了一个元素范围。在这种情况下,低和高将是相同的,因为它们引用数组上的相同索引。因此,您只需要在索引中返回该特定元素即可(您无需进行任何搜索,如果要在一个元素范围内搜索最大元素,则最大元素就是该单个元素)。返回a [low]或a [high]是相同的。

如果给定的范围包含多个元素,则进入else部分。

在这里,您将获得范围的中间索引。

因此,如果您指定了从索引3(低)到索引7(高)的范围,则中间索引将为5。(*(低+高)/ 2 *)

然后,您将范围划分为两个范围,左范围和右范围,它们都来自相同的原始范围,该范围被一分为二。

然后,对两个范围中的每一个执行我上面所述的所有操作,直到在同一点上拆分了这么多范围,最后得到一个元素范围,然后将其返回。

让我们在这里停留一秒钟。

看一下代码,我们将拆分范围的返回值分别存储在leftmax和rightmax中,但是由于您调用的是同一方法,因此每个拆分范围也将拥有自己的leftmax和rightmax以及自己的拆分范围。

就像您正在深入研究,表面是该方法的最初执行。

深度的最后一个级别给出一个元素范围(先前拆分的结果)。在这种情况下,该方法将停止调用自身,因为它实际上将返回一个值。谁将获得此返回值?前一个级别(也可能很深),该深级别将捕获最后一个级别的返回值并在代码中进行比较,即返回max元素,并将这两个数字的max元素返回到在它上面的水平,将执行相同的操作,然后将其返回更高的水平,然后不断地直到到达表面水平,并分别获得每个拆分数组的两个最大数目,然后检查这些最大数目两个数字并将其返回给您(您是最高级别!)。

我希望我能清楚地解释整个过程并为您提供帮助!!

10-08 00:18
查看更多