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

Question

这是一些Java代码，以递归方式反转字符串。有人可以解释一下它是如何工作的吗？public static String reverse(String str) {    if ((null == str) || (str.length() <= 1)) {        return str;    }    return reverse(str.substring(1)) + str.charAt(0);}我不明白这可能如何工作。

Answer 1

该函数采用String的第一个字符str.charAt(0)-将其放在末尾，然后调用自身reverse()-在其余部分上调用- str.substring(1)将这两件事加在一起即可得到结果-reverse(str.substring(1)) + str.charAt(0)

当传入的String为一个字符或更少个字符时，将没有剩余-当str.length()  <= 1)-它停止递归调用自身并仅返回传入的String。

因此运行如下：

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"

Answer 2

您需要记住，您不会只有一个电话-您将有嵌套电话。因此，当“嵌套程度最高的”调用立即返回时（当发现“ o”时），将进行下一个升级str.charAt(0)-此处str的“ lo”在哪里。这样就返回“ ol”。

然后，下一个水平将收到“OL”，执行str.charAt(0)用于其的值str（这是“LLO”），返回“OLL”下一级进行。

那么下一个水平将收到来自它的递归调用的“OLL”，执行str.charAt(0)了它的价值str（这是“ELLO”），返回“欧莱”到一个新的水平了。

然后最后一级将收到来自它的递归调用的“OLL”，执行str.charAt(0)了它的价值str（这是“你好”），返回“2009东海生日贺”到原来的调用者。

边走边考虑堆栈可能很有意义：

// 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" 

Answer 3

因为这是递归的，所以每一步的输出都是这样的：

输入“ Hello”。然后该方法用“ ello”调用自身，并将返回结果+“ H”

输入“ ello”。该方法使用“ llo”调用自身，并将返回结果+“ e”

输入“ llo”。该方法使用“ lo”调用自身，并将返回结果+“ l”

输入“ lo”。该方法使用“ o”调用自身，并将返回结果+“ l”

输入“ o”。该方法将满足if条件并返回“ o”

现在来看结果：

总的返回值将为您提供递归调用的结果加上第一个字符

从5返回的值将为：“ o”

从4的返回将是：“ o” +“ l”

3的返回值将是：“ ol” +“ l”

2的返回值是：“ oll” +“ e”

从1的返回将是：“ olle” +“ H”

这将为您提供“ olleH”的结果