Método recursivo para invertir una palabra, error StackOverFlow

publicado por: Anonymous
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;
}

Al hacer este método de invertir una palabra, me salta el error de StackOverFlow. Supongo que se habrá salido de la cadena o algo, pero no sé exactamente el error.

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)

solución

Problema. Antes de ir a la respuesta, veamos esta llamada que estás haciendo:

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

Si la palabra tuviese 10 caracteres, se estaría llamando recursivamente a la función con un string de largo ……..

¿Se ve ya el problema?

¡¡¡Sí, de 10 caracteres también!!!… O sea, las llamadas recursivas para invertirPalabra("abc") estarían siendo:

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

Claramente jamás se va a cumplir la condición if(palabra.length()==0){.

No redujimos ningún caracter en la llamada recursiva. ¿Esa tendría que ser la idea, no?

Bueno, ese es el problema.


Solución. ¿Y si llamamos recursivamente a la función solamente con lo que falta invertir?

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

Así, para invertirPalabra("abc") lograríamos:

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

Código:

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;
}

Demo:

http://ideone.com/iXj5az


Extra. Si te interesa acortar un poco más el código:

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

Leave a Reply

Your email address will not be published.