Cómo Reverse una cadena en Java usando recursividad

En este programa de ejemplo, invertiremos una cadena ingresada por un usuario.

Crearemos una función para invertir una cadena. Later Lo llamaremos recursivamente hasta que todos los caracteres estén invertidos. La recursión es adecuada para este problema porque una cadena invertida es simplemente la cola invertida de la cadena con el primer carácter original añadido al final, lo que representa el mismo problema con un carácter menos.

Escribir el Java Programa para Reverse Cordón

La clase que se muestra a continuación declara la entrada en main(), la pasa a reverseString() e imprime el resultado. Dos llamadas a println() dentro del método hacen que cada paso recursivo sea visible en la consola.

package com.guru99;
 
public class ReverseString {
 
	public static void main(String[] args) {
 
 
		String myStr = "Guru99";
 
 
		//create Method and pass and input parameter string 
		String reversed = reverseString(myStr);
		System.out.println("The reversed string is: " + reversed);
		
	}
 
 
	//Method take string parameter and check string is empty or not
	public static String reverseString(String myStr)
	{
		if (myStr.isEmpty()){
		 System.out.println("String in now Empty");	
		 return myStr;
		}
		//Calling Function Recursively
		System.out.println("String to be passed in Recursive Function: "+myStr.substring(1));
		return reverseString(myStr.substring(1)) + myStr.charAt(0);
	}
 
}

Code Salida:

Cada línea de la salida representa una llamada recursiva. El último carácter impreso en cada línea es un carácter más corto que el de la línea anterior, y la última línea muestra el resultado invertido.

String to be passed in Recursive Function: uru99
String to be passed in Recursive Function: ru99
String to be passed in Recursive Function: u99
String to be passed in Recursive Function: 99
String to be passed in Recursive Function: 9
String to be passed in Recursive Function: 
String in now Empty
The reversed string is: 99uruG

Cómo la recursiva Reversal Works Paso a Paso

Dos líneas contienen todo el método. El caso base, if (myStr.isEmpty()), le da a la recursión un punto donde detenerse. La línea recursiva, return reverseString(myStr.substring(1)) + myStr.charAt(0), divide el trabajo en dos: substring(1) es todo lo que sigue al primer carácter, y charAt(0) es ese primer carácter, agregado. después el resto invertido.

Tracla entrada GuruEl número 99 deja clara la orden. Java Envía un fotograma por cada llamada antes de que se produzca cualquier concatenación:

La pila se desenrolla de abajo hacia arriba y cada marco agrega su carácter guardado: la cadena vacía se convierte en 9, luego en 99, luego en 99u, 99ur, 99uru y finalmente 99uruG. Porque Java Las cadenas son inmutables; ninguno de estos valores intermedios sobrescribe el anterior: cada concatenación asigna un nuevo objeto String.

Hay dos detalles en la salida de la consola que merecen ser mencionados. La sexta línea termina vacía después de los dos puntos, ya que la función substring(1) aplicada a una cadena de un solo carácter devuelve la cadena vacía en lugar de null. El mensaje que sigue dice "String in now Empty" en el programa original; la frase es un error tipográfico y debería decir "String is now empty", por lo que se ha dejado sin modificar para que el código y la salida anterior coincidan línea por línea.

Otras formas de Reverse una cadena en Java

La recursión es la forma más clara de ver La reversión puede ocurrir, pero rara vez se realiza de la forma en que lo hace el código de producción. Tres alternativas cubren casi todos los casos reales.

1. StringBuilder.reverse() es la más corta y la más rápida. La clase incluye un método reverse() integrado, por lo que todo el trabajo cabe en una sola línea:

String reversed = new StringBuilder(myStr).reverse().toString();

2. Un bucle for con charAt() Recorre la cadena hacia atrás desde el último índice hasta cero. Los entrevistadores suelen pedir esta versión porque muestra la lógica en lugar de delegarla:

String reversed = "";
for (int i = myStr.length() - 1; i >= 0; i--) {
    reversed = reversed + myStr.charAt(i);
}

3. Un intercambio de dos punteros a toCharArray() convierte la cadena en una matriz de caracteres y luego intercambia los caracteres más externos hacia adentro hasta que los punteros se encuentran en el medio:

char[] chars = myStr.toCharArray();
int left = 0;
int right = chars.length - 1;
while (left < right) {
    char temp = chars[left];
    chars[left] = chars[right];
    chars[right] = temp;
    left++;
    right--;
}
String reversed = new String(chars);

La misma técnica de matriz invierte una secuencia numérica o cualquier otra colección ordenada, razón por la cual aparece en Java matriz ejercicios con la misma frecuencia que en los de cuerda.

Complejidad temporal y espacial de cada enfoque

Las cuatro versiones no cuestan lo mismo. Ambas entradas cuadráticas que aparecen a continuación comparten una causa: crean una cadena completamente nueva en cada paso, y copiar n caracteres n veces supone un trabajo de n al cuadrado.

Elija la versión recursiva para aprender o para demostrar cómo se comporta la pila de llamadas, la versión de matriz de caracteres cuando un entrevistador pida la lógica a mano, y StringBuilder.reverse() en cualquier cosa que se distribuya. La misma compensación entre una solución de enseñanza y una de producción aparece en todos los ejercicios clásicos, desde ordenamiento de burbuja y conectar Serie de Fibonacci a comprobaciones de números primos; vale la pena practicar cada uno de ellos Java en ambos sentidos.

Preguntas Frecuentes