¿Cuál es la mejor manera de explicar este método recursivo en Java?

Las dos primeras estructuras de control ( si (…) {…} ) son esencialmente las mismas, por lo que una de ellas es innecesaria. Si str.equals (“”) (o str.length == 0 ; El <= es un arenque rojo, ya que la longitud de un String no puede ser negativa), uno llega al caso base, donde termina la recursión. Posteriormente, la pila de llamadas se desenrolla. No puede golpear el caso base infinito muchas veces, porque no contiene recursividad.

La función miembro str.substring (int n) devuelve la subcadena de str que comienza en la posición n. Entonces, la llamada str.substring (1) devuelve str sin el primer carácter. La parte

if (str.charAt (0) == ‘x’) {
return “y” + changeXY (str.substring (1));
}

devuelve una cadena con el primer carácter cambiado a ‘y’ y recursivamente llama a changeXY () en la cola de str , pero solo si el primer caracter es igual a ‘x’ . Las llamadas posteriores de changeXY () cortan siempre el primer carácter y lo cambian a ‘y’ si es igual a ‘x’ o lo mantienen de otro modo, debido a

return str.charAt (0) + changeXY (str.substring (1));

mientras llama recursivamente changeXY () en el resto de la cadena.

En la última llamada a changeXY () , cuando el argumento no tiene más caracteres, la función golpea el caso base y desenrolla la pila de llamadas. (El caso base siempre se ve afectado por fin, porque la longitud del argumento String of changeXY () se reduce en uno en cada recursión. Por lo tanto, la secuencia de recursiones termina finalmente.) Por lo tanto, como resultado, se obtiene una String, donde todos los caracteres ‘x’ se cambia a ‘y’ mientras los otros caracteres permanecen.

Por cierto: esta función no es segura ya que el argumento str podría ser nulo en su primera llamada y luego arroja una NullPointerException .

La función no sabe nada sobre combinar todas las llamadas. El operador ‘+’ es el responsable de combinar todo.

El operador ‘+’ solo necesita una cadena para hacer su trabajo y dado que el tipo de retorno de la llamada recursiva es una cadena, el operador con mucho gusto concatenará los resultados y devolverá un valor.

Cuando escriba o intente comprender funciones recursivas, no piense demasiado en profundidad. Simplemente confirme que el caso base es accesible y que cada llamada recursiva conduce al caso base y, finalmente, que su combinador está combinando los resultados correctos.

Mire su caso base y piense en lo que sucedería si le da a la función una cadena que coincida con el caso base; llegaría al caso base? Si es así, ¿qué se devolvería? De lo contrario, debe corregir su algoritmo moviendo el caso base más cerca de la parte superior.

Ahora mire su (s) caso (s) recursivo (uno a la vez), ¿la recursividad tiende hacia el caso base? Es decir, ¿es posible que las propiedades de los argumentos de la llamada recursiva coincidan alguna vez con las propiedades esperadas por el caso base? Si es así, continúe, de lo contrario, debe repensar esa llamada recursiva.

Ahora mira tu combinador – (‘+’) en este caso – ¿Construye correctamente el resultado que deseas? Si es así, ya está listo; de lo contrario, corrija la forma en que combina los resultados.

¡Eso es! La recursión es en realidad mucho más fácil de entender que los métodos iterativos (al menos para mí) porque le permite separar (y reutilizar) la lógica para el cálculo de la lógica para generar resultados. Esto realmente puede ser beneficioso para comprender la lógica detrás de un fragmento de código.

Creo que una excelente manera de entender este algoritmo es implementarlo y ejecutarlo en algunos ejemplos, incluso mejor si está en un IDE en modo de depuración: realmente verá por qué funciona.

A partir de la cadena vacía, si se le da al método como una entrada, no hay una llamada recursiva: devuelve inmediatamente la cadena vacía en sí (primera instrucción “si”). La segunda declaración “si” es irrelevante, ya que se atravesará solo si la primera es, por lo tanto, no se puede alcanzar.

Las instrucciones restantes son la recursión real: el método devuelve el carácter actual (o “y” si el carácter actual es “x”), concatenado con el resultado de la llamada recursiva en la subcadena realizada desde el segundo hasta el último carácter. Por ejemplo, si llama al método en “xeox”, tendrá el siguiente árbol de recursión:

changeXY (“xeox”)

“Y” + changeXY (“eox”)

“Ye” + changeXY (“buey”)

“Yeo” + changeXY (“x”)

“Yeoy” + changeXY (“”)

“Yeoy”.

Para comprender la recursividad, sugeriría enfatizar la comprensión de la pila y el alcance variable primero. Para fines de demostración, agregué una variable de retorno para que ahora quede más claro cómo funcionan los valores de retorno de las expresiones con las funciones. Aquí está el código modificado, que puede ejecutar usted mismo:

clase pública HelloRecursiveWorld {

Public static String changeXY (entrada de cadena, profundidad int) {
System.out.println (“changeXY llamado, la cadena de entrada es: \” “+ input +” \ “, profundidad:” + profundidad);
if (input.equals (“”) || input.length () <= 0) {
System.out.println (“return: \” \ “” + “, profundidad:” + profundidad);
regreso “”;
}

if (input.charAt (0) == ‘x’) {
Cadena returnv =
“y” // Poner el carácter y en la variable de pila de retorno
+
changeXY (input.substring (1), profundidad + 1); // llamar a la función con el resto de la cadena de entrada y concatenarla a la variable de pila de retorno
System.out.println (“return: \” “+ returnv +” \ “, profundidad:” + profundidad);
return returnv;
}
más{
Cadena returnv =
input.charAt (0) // Poner el carácter de la cadena de entrada en la posición 0 para devolver la pila
+
changeXY (input.substring (1), profundidad + 1); // invoca recursivamente la función con el resto de la cadena de entrada y la concatena a la variable de pila de retorno
System.out.println (“return: \” “+ returnv +” \ “, profundidad:” + profundidad);
return returnv;
}
}

public static void main (String [] args) {
System.out.println (changeXY (“xopx”, 0));
}
}

El resultado es:

Se llama a changeXY, la cadena de entrada es: “xopx”, profundidad: 0

Se llama a changeXY, la cadena de entrada es: “opx”, profundidad: 1

Se llama a changeXY, la cadena de entrada es: “px”, profundidad: 2

Se llama a changeXY, la cadena de entrada es: “x”, profundidad: 3

Se llama a changeXY, la cadena de entrada es: “”, profundidad: 4

regresando: “”, profundidad: 4

regresando: “y”, profundidad: 3

regresando: “py”, profundidad: 2

regresando: “opy”, profundidad: 1

regresando: “yopy”, profundidad: 0

Puede ver que la función siempre solo maneja el primer carácter, luego pasa el resto de la cadena a una llamada recursiva. En cuanto a cómo funciona la pila, puede ver que el orden en que las llamadas devuelven valores son exactamente lo opuesto a la invocación. Esto se debe a que la llamada recursiva es esencialmente antes de que la función devuelva su valor, más exactamente dicho, la función necesita el resultado de su llamada recursiva para devolver su resultado.

La clave para entender cualquier recursión es esta:

• Proporcione un valor para un caso base. Aquí esto se hace con la cadena vacía tge del caso base.
• Proporcione el valor para una entrada arbitraria expresándola en términos del valor que es “más pequeño” que la entrada. En este caso, se expresa obteniendo el valor de la función para una cadena que es una más corta y aplicando algunas operaciones. Esto asegura que siempre se alcance el caso base y se detenga la recursividad.

En términos abstractos:

Base: [matemática] r (x) = f_1 (x) [/ matemática] si [matemática] s (x) = 0 [/ matemática]

Caso recursivo: [matemática] r (x) = f_2 (x, r (g (x))) [/ matemática] donde [matemática] s (g (x))

aquí

Esta es una demostración de un enfoque funcional del problema que está tratando de resolver. Piensa en tu cadena como una lista de caracteres. Su función opera en el primer carácter y deja el resto para otra función que resulta ser ella misma. La concatenación continúa hasta que se consume toda la cadena y llega a su caso de terminación.

Apátrida (aparte de la pila, por supuesto). La pila crecerá hasta que llegue al final de la cadena, momento en el que tendrá su retorno de terminación y todo colapsará para darle el resultado de su llamada original.

Tienes otras respuestas que explican cómo funciona. Otras dos cosas que vale la pena mencionar son:

Llamar ciegamente str.substring (1) cuando no sabe si es un índice válido es una mala práctica. Puede funcionar en Java y obtener una cadena vacía, pero si está aprendiendo a programar (en lugar de solo aprender Java), tenga en cuenta que esto explotará con una violación de acceso en un lenguaje como C (o peor, devuelva basura aleatoria )

No use la recursividad para cosas como esta, especialmente en Java (que no tiene optimización de llamadas de cola). Está quemando espacio en la pila sin una buena razón, por lo que es vulnerable a una excepción StackOverflow con una gran entrada. Esto debe hacerse con un simple for loop.

No conozco demasiado a Java, pero parece que el caso base devuelve un valor real, por lo que parece que no sería infinitamente recursivo. La combinación ocurre ya que agrega y luego se llama a sí misma en el resto.

changeXY (“xeoy”) = “y” + changeXY (“eoy”) = “y” + (”e” + changeXY (“oy”)) = “y” + (”e” + (”o” + changeXY (“Y”))) = “y” + (“e” + (“o” + (“y + changeXY (“ ”)))) =“ y ”+ (“ e ”+ (“ o ”+ ( ”Y” + ””))) = “yeoy”

Supongo que la adición de cadenas en Java es concatenación.

changeXY (“xeox”) = “y” + changeXY (“eox”)

changeXY (“eox”) = “e” + changeXY (“ox”)

changeXY (“ox”) = “o” + changeXY (“x”)

changeXY (“x”) = “y”

Así “xeox” se convierte en “yeoy”