Home / Questions / 48956
Accepted
RoyalUp
Asked: 2020-02-12 04:48:16 +0800 CST 2020-02-12 04:48:16 +0800 CST

递归方法反转一个单词，StackOverFlow 错误

  • 772
private static String invertirPalabra(String palabra) {
    String res = "";

    if(palabra.length()==0){
        res = palabra;
    }else{
        res = invertirPalabra(palabra.substring(1)+ palabra.charAt(0));

    }
    return res;
}

在执行这种反转单词的方法时，我得到了 StackOverFlow 错误。我想它一定是脱链了或其他什么，但我不知道究竟是什么错误。

Exception in thread "main" java.lang.StackOverflowError
  at java.lang.String.<init>(Unknown Source)
  at java.lang.String.substring(Unknown Source)
  at Ejemplo2.invertirPalabra(Ejemplo2.java:70)
java

3 Answers

  1. Best Answer

    问题。在我们得到答案之前，让我们看看你正在打的这个电话：

    invertirPalabra(palabra.substring(1)+ palabra.charAt(0));

    如果单词有 10 个字符，它将递归地调用带有长字符串的函数........

    你现在能看出问题了吗？

    是的，也是 10 个字符！！！... 换句话说，递归调用invertirPalabra("abc")将是：

    invertirPalabra("bca")
invertirPalabra("cab")
invertirPalabra("abc")
invertirPalabra("bca")
...

    显然这个条件永远不会满足if(palabra.length()==0){。

    我们没有减少递归调用中的任何字符。应该是这样的想法吧？

    嗯，这就是问题所在。


    解决方案。如果我们递归地调用函数，只剩下要反转的东西怎么办？

    res = invertirPalabra(palabra.substring(1)) + palabra.charAt(0);
//                                          ^^^^^^^^^^^^^^^^^^^
//                                Esto no se está pasando como parámetro
//                                Sólo se está devolviendo como resultado de la función

    因此，要invertirPalabra("abc")实现：

    invertirPalabra("bc") + "a"
   ^-- invertirPalabra("c") + "b"
          ^-- invertirPalabra("") + "c"
                 ^-- ""


    代码：

    private static String invertirPalabra(String palabra) {
    String res = "";

    if(palabra.length() == 0){
        res = palabra;
    }else{
        res = invertirPalabra(palabra.substring(1)) + palabra.charAt(0);
    }
    return res;
}

    示范：

    http://ideone.com/iXj5az


    额外的。如果您有兴趣进一步缩短代码：

    public static String invertirPalabra(String palabra) {
    if (palabra.length() <= 1) {
        return palabra;
    }
    return invertirPalabra(palabra.substring(1)) + palabra.charAt(0);
}
    • 4

  2. 如果是关于递归，那么我们必须很好地考虑基本情况和递归情况：

    最好用图片来解释

    在此处输入图像描述

    在代码中它将是：

    public String invertirPalabra(String palabra){
    if (palabra.length() == 1){
        return palabra;
    }
    return invertirPalabra(palabra.substring(1)) + palabra.charAt(0);
}
    • 3

  3. 递归解决方案：

        public static String invertirPalabra(String palabra)
    {
      if (palabra.length() <= 1) 
      {
        return palabra;
      }
      return invertirPalabra(palabra.substring(1)) + palabra.charAt(0);
    }

    使用 StringBuilder 类的非递归解决方案：

        public static String invertirPalabra(String palabra)
    {
      return new StringBuilder(palabra).reverse().toString();
    }
    • 2