在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

该函数接受一个字符串的第一个字符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"

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"