有人能解释一下使用尾部递归的反向字符串算法吗

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"

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

Answer 2

当方法运行时，它将首先检查字符串的长度是一个字符还是零个字符。这将告诉它它是否是字符串中的最后一个字符。如果没有，它将把当前字符附加到字符串的末尾，然后再次运行，这次是在下一个字符上运行。这意味着字符串每次都会变短一个字符。

可能令人困惑的是，str.charAt(0)并没有传递到方法的下一次迭代中，而只是作为返回语句的一部分添加。这意味着，一旦该方法完成了最后一个字符，它将以向后的顺序返回所有字符，因为每个方法从返回最后一个角色的方法开始一个接一个地完成。这种情况将一直发生，直到所有方法都返回并返回反向字符串。

这就像方法的层，一个方法将调用另一个方法，然后它们都将按照调用顺序向后完成。

希望这能帮助你理解！

Answer 3

没有问题就是愚蠢的问题。如果一个人不问一个问题，以为人们会认为他/她很愚蠢，那么他/她一生都很愚蠢

现在解释一下：

我添加了一个打印声明来帮助您。

public static String reverseRecursively(String str) {
System.out.println("For debuging : "+str); // this is my print statement.
if (str.length() < 2) {
return str;
}
return reverseRecursively(str.substring(1)) + str.charAt(0);
}

它打印下面的内容。

For debuging : abcd
For debuging : bcd
For debuging : cd
For debuging : d
dcba

方法返回值的基本条件是str.length() < 2。

因此，当最后一个方法调用(或者我们可以说是对reverseRecursively(String str)的第四个方法调用(返回"d"时，因为长度小于2。第三个方法调用将返回

"d" + "cd".charAt(0);

它只不过是：dc。

类似的第二种方法将使用第三种方法的返回值(dc(并返回值

"dc" + "bcd".charAt(0);

即dcb。

因此，第一个方法调用将返回，在该方法调用中，您传递了字符串"abcd"作为输入。

"dcb" + "abcd".charAt(0);

即dcba。

希望这能有所帮助。干杯

Answer 4

`public static String reverseRecursively(String str) {
if (str.length() < 2) {
return str;
}
return reverseRecursively(str.substring(1)) //take "bcd" : 1st Itration
//"cd" : 2nd 
// "d" : 3rd (this makes str.length() < 2)
// 3rd returns first with "d" and pass control back to 2nd recursion
//2nd takes d and adds 0th char c and returns with "dc" and pass control to 1st
//1st takes dc and adds b returns with "dcb" and pass control to base call
// base call take "dcb" and adds 0th char a and returns to calling method
+ str.charAt(0);
}`.