在 java 中尝试使用递归查找字符串的反转时出现 StackOverflowError

Question

我正在尝试使用递归来查找字符串的反转，但是当我运行我的代码时出现 Whosebugerror。我是递归的新手，所以我不确定我需要做什么来修复它。

public static String reverse(String string) {
        int index = 0;
        if(string == null){
            return " ";
        }
        else if(index < string.length()) {
            char a;
            a = string.charAt(index);
            index += 1;
            return a + reverse(string);
        }
        return " ";
    }

Answer 1

您似乎缺少的部分是将索引传递给您的函数。另外，当你递归时，你需要 return 最后的当前字符。我想你想要像

这样的东西

private static String reverse(String string, int index) {
    if (string != null && index < string.length()) {
        char a = string.charAt(index);
        return reverse(string, index + 1) + a;
    }
    return "";
}

然后您在 public 接口中的方法可以调用初始 index 为 0 的函数，例如

public static String reverse(String string) {
    return reverse(string, 0);
}

当然，在实际代码中我更喜欢 StringBuilder 之类的

public static String reverse(String string) {
    StringBuilder sb = new StringBuilder(string);
    return sb.reverse().toString();
}

Answer 2

有很多问题。我添加了一些评论来尝试提供帮助。

public static String reverse(String string) {
    int index = 0;
    if(string == null){
        return " ";
    }
    /* This will always be true because index is always zero */
    else if(index < string.length()) {
        char a;
        /* This gets the character at position zero */
        a = string.charAt(index);
        /* This increments zero by 1 */
        index += 1;
        /* This takes the character and then calls reverse again (the recursion.
           The problem is that you are passing the full string in and so every time
           you recurse, index will be zero again and the string will be exactly the same length.
           So no exit criterion will ever be triggered. 
           As such this is an infinite recursion. */
        return a + reverse(string);
    }
    return " ";
}

我建议考虑以下几点：

在最后一次递归调用时，即当您开始 "pop back" 通过每个递归调用时，您希望触发它的是什么？
如果您决定在每次递归调用中通过删除第一个字符来缩短字符串，那么最后一次调用将是一个空字符串。
另一方面，如果您决定最后一次调用是索引变量等于字符串长度，那么您将需要考虑传入一个额外的参数（索引）并在每次调用时将其增加一个递归调用。

Answer 3

这不是递归的工作方式，因为您只是一遍又一遍地传递相同的字符串。您可以使用递归，但有两种方法可以解决您的问题。

获取最后一个字符并使用没有最后一个字符的字符串调用该方法，如下所示：

public String reverse(final String string) {
    if (string != null && !string.isEmpty()) {
        final int length = string.length();
        final char character = string.charAt(length - 1));  
        final String result = reverse(string.substring(0, length - 2));
        if (result != null)
            return String.valueOf(character) + result;
        return String.valueOf(character);
    }
    return null;
}

我不应该因为我没有对此进行测试，但关键是我正在更改传递的字符串并且有一种机制来检测何时停止调用我自己的方法。

第二种方法是不用递归来完成，因为你可以用一些for循环等来完成。但是为了学习，检查 1 :P

Answer 4

每次调用递归方法时，您都在初始化变量 "index and a"。初始化方法块外的所有变量。试试这个功能..

public static String reverse(String str){

    if(str.length()<=0||str.length()==1)
        return str;
    return reverse(str.substring(1))+str.charAt(0);
}

在 java 中尝试使用递归查找字符串的反转时出现 StackOverflowError

StackOverflowError when trying to find the reverse of a string using recursion in java

java

recursion