recursivo - recursividad en java pdf

¿Convertir una función recursiva en un ciclo for?

Question

¿Cada función recursiva tiene un equivalente para el ciclo? (Ambos logran el mismo resultado).

Tengo esta función recursiva:

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    if(words[length].contains(word.substring(0, length)))
        return recur(word.substring(length), word.length() - length);
    return recur(word, length-1);
}

Dado que las palabras son un conjunto [], y donde las palabras [i] = un conjunto con palabras de longitud i.

Lo que trato de hacer es: iniciar la recursión con una palabra (por ejemplo, "stackoverflow", sin espacios), estoy tratando de encontrar si esta palabra se puede cortar en subwords ("pila", "sobre", "flujo") .. la longitud mínima de una subpalabra es 3, y dado que la subpalabra de longitud i está en las palabras establecidas [i].

Puedo confirmar que este código funciona, pero puede tener un problema de memoria, por lo que quiero convertirlo en un bucle ... si es posible.

¿¿Necesitas más información??

Gracias.

Answer 1

@biziclop muestra cómo refactorizar el código para que no sea recursivo. Yo iría más allá y reduciría el código para que así sea.

• La length ya no se pasa como argumento.
• Dos bucles se utilizan para simplificar la lógica.
• modificar el valor de la palabra local para simplificar.

código

private static boolean recur(String word) {
    LOOP: for(;;) {
        for (int len = word.length(); len >= 3; len--)
            if (words[len].contains(word.substring(0, len))) {
                word = word.substring(len);
                continue LOOP;
            }
        return word.length() == 0;
    }
}

Answer 2

La recursividad de la cola siempre se puede desenrollar en un bucle y su código está bastante cerca de la recursividad de la cola, entonces sí.

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    int nextLength;
    String nextWord;
    if(words[length].contains(word.substring(0, length))) {
      nextWord = word.substring(length);
      nextLength = word.length() - length;
    } else {
      nextWord = word;
      nextLength = length - 1;
    }
    return recur(nextWord, nextLength);
}

Esta es ahora la recursión de cola adecuada. Ahora para convertirlo en un bucle:

private static boolean recur(String word, int length) {
    int nextLength = length;
    String nextWord = word;
    while( true ) {
        if(nextLength == 1 || nextLength == 2)
            return false;
        if(nextLength == 0)
            return true;
        if(words[nextLength].contains(nextWord.substring(0, nextLength))) {
            nextWord = nextWord.substring(nextLength);
            nextLength = nextWord.length() - nextLength;
        } else {
            nextWord = nextWord;
            nextLength = nextLength - 1;
        }
    }
}

Tenga en cuenta que este código se puede optimizar aún más, solo quería demostrar el método "automático" para convertir la recursividad en un ciclo.

Answer 3

Para la pregunta general: Sí, cada recursión se puede transformar en un ciclo. Puede modelar explícitamente la pila creada y utilizada por recursividad y modificarla en el ciclo.

Para el problema específico:

Al ver su código como una función e ignorar los efectos secundarios, creo que puede devolver falso.

Si realmente necesita las palabras divididas intente lo siguiente:

have a list with the word to split.
iterate until list after iteration is the same as before.
    iterate over list
        if the word can be split, replace it in the list with its parts
    end of loop
end of loop

Answer 4

Respondo su primera pregunta: Sí, cada función recursiva tiene un equivalente iterativo. Leer más

Esto también está relacionado con CPS (no exactamente porque las llamadas de cola no son realmente compatibles con las populares máquinas virtuales de Java). La conversión de una función recursiva de cola (como la de la pregunta) debería ser especialmente fácil.

Answer 5

Respuesta corta: en general puede, en este caso puede hacerlo fácilmente, pero si soluciona el error en la lógica de su código, debe preocuparse por mantener una pila usted mismo.

Respuesta larga:

Primero, la versión iterativa de su método recursivo:

private static boolean recur(String word, int length) {
    while(true) {
        if(length == 1 || length == 2)
            return false;
        if(length == 0)
            return true;
        if(words[length].contains(word.substring(0, length))) {
            int newlen = word.length() - length;
            word = word.substring(length);
            length = newlen;
        }
        else {
            --length;
        }
    }
}

Esto funciona reemplazando la llamada recursiva por asignación a los parámetros y pegándola todo en un bucle.

Pero al igual que su código original, ¡esto contiene un error!

(No puedo pensar en palabras reales con las que funciona este error, así que imagina que mis palabras inventadas son palabras reales).

Supongamos que su palabra larga es ABCDEFGH, y que ABCD, EFGH y ABCDE son todas palabras, pero FGH no lo es. recur busca la palabra más larga primero, por lo que coincidirá con ABCDE, luego descubre que FGH no es una palabra, y le dice que ABCDEFGH no se puede cortar en subwords.

¡Pero podría dividirse en ABCD y EFGH! Se pierde la coincidencia inicial más corta porque no considera otras opciones una vez que ha encontrado una coincidencia. (Y si su código comenzó buscando la coincidencia más corta, aún no funcionaría si ABC fuera una palabra y DEFGH no lo fuera).

Asi que:

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    return (words[length].contains(word.substring(0, length)))
            && recur(word.substring(length), word.length() - length))
           || recur(word, length-1);
}

Ahora, convertir esto en un método iterativo es más difícil: a veces tiene dos llamadas recursivas. Eso significa que simplemente asignar sus parámetros no funcionará, porque necesita los valores originales de los parámetros para calcular los parámetros para la segunda llamada. Tiene que administrar explícitamente una pila o una cola con todos los valores diferentes, porque ahora el idioma no lo está haciendo por usted.