更好地理解Java中的递归

minindex 直到 findShortestString 回报 ,直到 lo == hi .

每次方法调用自身时,它都会缩小 lo 和 hi 乘以1,所以最终它们将相等*并且该值将被返回。

一个例子 paths = ["p1", "path2", "longpath3"] :

lo = 0, hi = 2
lo != hi -> call findShortestString(paths, 1, 2)

  lo = 1, hi = 2
  lo != hi -> call findShortestString(paths, 2, 2)

    lo = 2, hi = 2
    lo == hi -> return lo (=2)

  lo = 1, hi = 2, minindex = 2
  length of "path2" < length of "longpath3" -> return lo (= 1)

lo = 0, hi = 2, minindex = 1
length of "p1" < length of "path2" -> return lo (= 0)

我试图通过增加缩进量来说明每个递归级别的变量值。在每次递归调用开始时,前面的值 低 , 你好 和 minindex公司 保存(在称为“堆栈”的结构中)并使用新值。每次调用方法时 回报 ,先前保存的值将从堆栈中“弹出”以供使用,并且 minindex公司 从上一个返回值分配。

*除非首先是“你好”,我想。。。

以下是执行的一个剧本:

你打电话来 findShortestString() 你自己

如果lo不等于hi,事情继续。否则它们在这里停止,函数返回。

一旦你打电话 findShortestString() 同样,这个函数实例中的所有内容都将完全停止,直到计算机有一个值可以给出 minindex (也称为函数返回。)我们在顶部的函数的新实例中重新开始。在其中一个函数返回之前执行的唯一代码是方法调用之前的代码。这可以比作一个while循环。

只有当一个函数实例 lo==hi 然后回来。

控件切换到之前的函数实例,该实例将 lo 价值 minindex公司 .

如果 (safeStringLength(paths[lo])<safeStringLength(paths[minindex])) 然后我们 return lo . 否则,我们 return minindex . 不管怎样,这个函数实例是完整的,控件返回到它之前的那个。

每个被调用的函数现在只在方法调用之后执行代码,因为方法不会被再次调用。我们正在展开一堆调用。现在所有的返回都来自最后两个语句,因为顶部的代码不会再次执行。注意只有一个函数实例返回代码的顶部,从而终止while循环。在递归调用之后,所有剩余部分都以函数部分中的return语句结束。

最后,最后一个函数返回,然后返回到最初调用该函数的代码。

下面是代码实际工作的可读性更强的版本:

在递归调用之前的代码中,只会创建一个调用链,直到 低==高 . 每次调用函数时,lo值都是1。下面是一组调用示例:

findShortestString(2,5);
findShortestString(3,5);
findShortestString(4,5);
findShortestString(5,5);

当它们展开时,每个函数实例都会比较索引lo处字符串的长度,并将前一个索引处的字符串长度与最短的字符串进行比较。

compare strings at indexes 2 and 5
if the string at 2 is smaller, compare the strings at indexes 2 and 4.
Otherwise, compare the strings with indexes at 3 and 5.

如果 lo>hi 在开始时,代码将继续运行,直到lo溢出一个整数并变为负数,然后直到lo最终一直到hi,或4,94967296-(original lo-original hi)。换句话说,在 长时间 . 若要解决此问题,请在引发异常的方法的开头添加一个检查 低>高 .

代码可以更好地重写如下:

static int findShortestString(String[] paths, int lo, int hi) {
    int indexWithShortestString=lo;
    for( int i=lo; i<=hi-1; i++) {
        //assumption: lo and hi are both valid indexes of paths
        if (paths[i+1].length < paths[i].length)
            indexWithShortestString=i+1;
     }
}

想想一堆。每次调用递归方法时,都会在堆栈顶部放置一个新的“框架”。框架包含每个变量自己的“槽”,独立于下面框架中的槽。

最终,将创建一个新的框架,其中 lo 和 hi 是相等的,方法将返回 没有 推另一个框架。(这称为“基本情况”。) return 发生,该帧将从堆栈中弹出,位于其正下方的帧将在第二个时继续执行 if 陈述。最后,该帧也会弹出,下面的帧也会发生同样的情况,以此类推,直到执行返回到原始调用方。

每次 findShortestString 自称, minindex 最终将被赋值,然后在 if 陈述。它总是将最短字符串的索引设置为高于 lo .

如果有一个调用堆栈有10个findShortestString级别, minindex公司 被分配9次(第一次调用来自另一个函数)。

这是一个非常混乱的递归函数。但你一般都是对的。每次调用findShortestString()都会将函数推送到堆栈上。它会一直这样直到lo==hi。在这一点上,堆栈被解绕,相应的递归调用将被分配给它们相应的int。

在这个函数中,似乎只有 lo . 因为要么 (safeStringLength(paths[lo])<safeStringLength(paths[minindex]) 会是真的你会回来的 低 . 或者 lo==hi 会是真的你会回来的 低

为了陈述

int minindex=findShortestString(paths,lo+1, hi);

要计算,方法调用 findShortestString(paths,lo+1, hi) 必须返回值。因此 if 语句在此方法调用返回值之前不会发生。但是,此方法可能会再次调用自身,从而获得嵌套效果。

基本上,函数的执行在调用return语句时结束。在一个被称为“不再存在”(或“存在”)的返回语句之后的所有事物。

因此,当第一个if语句为false时,局部变量MNEDIQUE只存在于FUNCHOLTEST字符串函数的执行中。

独立处理findShortestString函数的每次执行,无论是递归调用还是从代码中的其他地方调用。i、 e.findShortestString函数的不同执行可能在不同的路径返回,并具有自己的值和局部变量。根据输入值,它们可能在第3、6或7行返回。

Min DUNDEX只存在于运行4行的执行中,并且它被分配了FixSuthTestStand(路径,LO + 1,HI),如果代码是正确的,则保证它有一个值,否则将得到无限递归,导致堆栈溢出(双关非故意)。