在 Java 中使用递归反转字符串

string reverse java recursion

2022-08-31 21:10:06

下面是一些以递归方式反转字符串的 Java 代码。

有人可以解释它是如何工作的吗？

public static String reverse(String str) {
    if ((null == str) || (str.length() <= 1)) {
        return str;
    }
    return reverse(str.substring(1)) + str.charAt(0);
}

我不明白这怎么可能起作用。

答案 1

该函数采用 String 的第一个字符 - - 将其放在末尾，然后调用自身 - - 在余数上 - ，将这两个东西相加以获得其结果 -str.charAt(0)reverse()str.substring(1)reverse(str.substring(1)) + str.charAt(0)

当在 String 中传递的字符串是一个字符或更少，因此将没有剩余部分时 - 当 - 它停止递归调用自身，而只是返回传入的字符串。str.length() <= 1)

因此，它按如下方式运行：

reverse("Hello")
(reverse("ello")) + "H"
((reverse("llo")) + "e") + "H"
(((reverse("lo")) + "l") + "e") + "H"
((((reverse("o")) + "l") + "l") + "e") + "H"
(((("o") + "l") + "l") + "e") + "H"
"olleH"

答案 2

您需要记住，您不会只有一个呼叫 - 您将有嵌套呼叫。因此，当“高度嵌套”调用立即返回时（当它只找到“o”时），下一个级别将采取 - 此时“lo”在哪里。因此，这将返回“ol”。str.charAt(0)str

然后下一级将收到“ol”，执行其值（即“llo”），将“oll”返回到下一级。str.charAt(0)str

然后下一级将从其递归调用中接收“oll”，为其值（即“ello”）执行，将“olle”返回到下一级。str.charAt(0)str

然后，最终级别将从其递归调用中接收“oll”，为其值执行（即“hello”），将“olleh”返回给原始调用方。str.charAt(0)str

在进行操作时考虑堆栈可能是有意义的：

// Most deeply nested call first...
reverse("o") -> returns "o"
reverse("lo") -> adds 'l', returns "ol" 
reverse("llo") -> adds 'l', returns "oll" 
reverse("ello") -> adds 'e', returns "olle" 
reverse("hello") -> adds 'h', returns "olleh"