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

Question

抱歉问这个问题太蠢了。在获取给定字符串的最后一个字符和 return 之前，我能够理解代码，然后我无法关联递归逻辑。

在此处发布之前，调试器部分帮助了我。不幸的是，不是 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() 放在 return 之前，您将获得以下输出：

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。

为什么会反过来呢？

嗯，你要想到调用trace：

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

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

Answer 2

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

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

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

希望这对您的理解有所帮助！

Answer 3

没有问题是愚蠢的问题。如果一个人不问一个问题，认为人们会认为 he/she 是愚蠢的，那么 he/she 就是一生的愚蠢。 :)

现在解释：

我添加了打印语句来帮助您。

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

return 值的方法的基本标准是，str.length() < 2。

所以当"d"被最后一个方法调用return编辑时（或者我们可以说第四次方法调用reverseRecursively(String str)），因为长度小于2。第三个方法调用将 return

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

这不过是 : dc.

类似的第二种方法将使用第三种方法的 return 值 (dc) 和 return 值

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

这是dcb。

所以第一个方法调用，您将字符串 "abcd" 作为输入传递给 return.

"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);
}`.

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

Could someone please explain the algorithm of reverse string using tail recursion?

java

tail-recursion