java - 更好地理解 Java 中的递归

Question

好吧，我真的对 Java 中的递归有些困惑。假设我有以下代码:

static int findShortestString(String[] paths, int lo, int hi) {
        if(lo==hi)
            return lo;
        int minindex=findShortestString(paths,lo+1, hi);
        if(safeStringLength(paths[lo])<safeStringLength(paths[minindex]))
            return lo;
        return minindex;

现在的问题不在于代码本身，而在于递归的工作原理。 minindex 被设置为等于递归调用。因此，函数第一次运行并尝试将 minindex 设置为某个值时，它会这样做，然后函数调用自身。但是 if 语句什么时候运行呢？它只会在 minindex 最终真正拥有实际值(value)时运行吗？我只是无法解决这个问题。如果 minindex 导致函数递归和递归，那么什么时候检查 if 语句？什么时候 lo==hi？我不明白:(

Answer 1

minindex 直到 findShortestString 返回 才会被赋值，直到 lo == hi 才会发生。

每次该方法调用自身时，它会将 lo 和 hi 之间的差异缩小 1，因此最终它们会相等*，并且会返回该值。

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

lo = 0, hi = 2lo != 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 = 1length of "p1" < length of "path2" -> return lo (= 0)

我试图通过增加缩进量来说明每个递归级别的变量值。在每次递归调用开始时，lo、hi 和 minindex 的先前值被保存下来(在称为“堆栈”的结构中) 和使用的新值。每次调用方法返回时，先前保存的值都会从堆栈中“弹出”以供使用，并根据先前的返回值分配minindex。

*unless lo > 首先你好，我想......