java - 有人可以解释一下使用尾递归的反向字符串算法吗？

Question

我很抱歉问这个问题是愚蠢的。在获取给定字符串的最后一个字符并返回之前，我能够理解代码，然后我无法关联递归逻辑。

在此处发布之前，调试器部分地帮助了我。不幸的是，不是 100%

你能帮我理解一下吗？

public static void main(String[] args) {
    System.out.println(reverseRecursively("abcd"));
}

public static String reverseRecursively(String str) {
    if (str.length() < 2) {
        return str;
    }
    return reverseRecursively(str.substring(1)) + str.charAt(0);
}

调试器输出:

0=abcd
1=bcd
2=cd
3=d
Final: dcba

Answer 1

嗯，这是一个非常简单的逻辑:

return reverseRecursively(str.substring(1)) + str.charAt(0);

如果您在返回之前放置一个 System.out.println()，您将获得以下输出:

Recursing with substring: bcd and adding a
Recursing with substring: cd and adding b
Recursing with substring: d and adding c
Adding d as final char

如果你反转它，你会得到 dcba。

为什么会反转呢？

好吧，你必须想到调用跟踪:

return reverseRecursively("bcd") + a -> retruns "dcba"
-> return reverseRecursively("cd") + b -> returns "dcb"
 -> return reverseRecursively("d") + c -> returns "dc"
   -> return d -> returns "d"

我想关键是要理解递归总是与另一个递归的结果相结合。