算法基本递归-在数组中搜索

我在递归方面遇到很多麻烦,包括其背后的逻辑。我知道原则上每当我们有一个循环时,都可以用对函数的调用来代替它。因此,我尝试了一个简单的示例(非常经典),在表中搜索最大值。这是Java迭代的经典示例:

static void rechercheMax(int unTab []) {
    int max = unTab[0];

    for (int j = 0; j < unTab.length; j++) {
        if (unTab[j] > max) {
            max = unTab[j];
        }
    }
    System.out.println("the  max is " + max);
}

如您所见,没有什么例外。另一方面,更难的是我制作的递归版本:

static int rechercheMaxRec(int[] unTab,int j,int max) {   
    if (j < unTab.length) {
        if (unTab[j] > max) {
            max = unTab[j];
            j++;
            rechercheMaxRec(unTab,j,max);
        }else {
            j++;
            rechercheMaxRec(unTab,max);             
        }
    } 
    return max;
}

我完全迷失了,这确实是一个“疯狂”的事情,就是一旦循环结束,计数器就朝相反的方向开始。老实说,我一点也不明白。

当我从主体调用函数时,操作如下

// the call from the main..... there is of course code preceding this:
int unTab [] = {7,22,11,34,17,52,26,13,40,20,103,10,5,16,8,4,2,1};
System.out.println ("The max in the recursive is" + searchMaxRec (unTab,0));

你能告诉我两件事吗?

  • 为什么没有给出正确的结果,并且
  • 为什么会朝相反的方向发展?

这种行为让我很不舒服;我担心我对递归一无所知。

jackychen101211 回答:算法基本递归-在数组中搜索

它没有给出正确的结果,因为您忘记了使用递归调用返回的值。实际上,您应该将其分配给SelectionChanged(这样它就会在函数中的最后一条语句中返回),或者只是立即将其返回。

它(也)朝相反的方向前进,因为这是递归的 backtracking 部分:首先,它进入(递归)更深的递归级别,然后到达最深的点(当{ {1}}条件不再成立),并从此结束返回到起点。这是stack的原理。它是先进先出(FILO)的处理顺序。因此,在“输入”部分(递归)中,您将获得正向订单;在“输出”部分中(递归)中,您将获得相反的订单。

请注意,您实际上并不需要对代码中的变量进行更改,例如maxif。您可以将更改后的值直接作为参数传递给递归调用:

j++

您甚至可以删除内部的max =开关(这只会对最后一个参数有所不同),而改为使用static int rechercheMaxRec(int[] unTab,int j,int max) { if (j < unTab.length) { if (unTab[j] > max) { return rechercheMaxRec(unTab,j+1,unTab[j]); }else { return rechercheMaxRec(unTab,max); } } return max; } 表达式:

if / else

即使可以通过三元运算符减少:

Math.max
,

关于“为什么没有给出正确的结果”

使用递归时,您将进行初始递归调用,而该递归调用本身将进行第二个调用,依此类推。初始调用将返回嵌套调用返回的结果,而嵌套调用本身将返回从嵌套调用返回的结果,等等。

此处的呼叫未返回正确结果的原因是您呼叫了rechercheMaxRec(unTab,0);,后者呼叫了 rechercheMaxRec(unTab,j,max);,但没有返回其结果。因此,发生的情况是,当您调用rechercheMaxRec(unTab,0);时,它将if (j < unTab.length)评估为true,然后将if (unTab[j] > max)评估为true,然后运行max = unTab[j];(即将max设置为7),然后调用 rechercheMaxRec(unTab,1,7);,但不返回rechercheMaxRec(unTab,7);返回的值。结果,在调用 rechercheMaxRec(unTab,7);之后,代码退出条件块并调用return max;,即返回7。

因此,基本上您想要的是将rechercheMaxRec(unTab,max);替换为return rechercheMaxRec(unTab,max);。这将返回103而不是7。

还有另一个问题不会影响您仅找到untab最大值的能力,但是如果您向代码中添加更多内容,则可能会导致其他问题。 untab的长度为18,因此,如果j == 17,您的代码将递增j,然后调用rechercheMaxRec(unTab,18,max);,这超出了范围。同样,这不会像原来那样导致代码出错,但是例如,如果您尝试System.out.println(...)的值untab[j],则会引发错误。

避免这种情况的方法是在递增j之后,再次检查是否为j < unTab.length,如果是,则调用rechercheMaxRec(unTab,max),如果不是,则只需返回max,因为在数组末尾。

这是解决两个问题的代码:

static int rechercheMaxRec(int[] unTab,int max) {
    if (j < unTab.length) {
        if (unTab[j] > max) {
            max = unTab[j];
            j++;
            if (j < unTab.length) {
                return rechercheMaxRec(unTab,max);
            } else {
                return max;
            } 
        }else {
            j++;
            if (j < unTab.length) {
                return rechercheMaxRec(unTab,max);
            } else {
                return max;
            }       
        }
    } 
    return max;
}

回复:为什么会朝相反的方向?

我不认为它是:)我认为它可能看起来像是这样做的,因为它返回7而不是103,但这只是因为如上所述的调用vs返回的概念。

让我知道是否还有不清楚的地方!

本文链接:https://www.f2er.com/3129496.html

大家都在问