Como Reverse uma string em Java usando recursão

Neste programa de exemplo, inverteremos uma string inserida por um usuário.

Criaremos uma função para reverter uma string. Later Chamaremos o processo recursivamente até que todos os caracteres sejam invertidos. A recursão é adequada para este problema porque uma string invertida é simplesmente a cauda invertida da string com o primeiro caractere original anexado ao final, que é o mesmo problema, porém com um caractere a menos.

Escreva para Java Programa para Reverse Tanga

A classe abaixo declara a entrada em main(), passa-a para reverseString() e imprime o que é retornado. Duas chamadas println() dentro do método tornam cada etapa recursiva visível no console.

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 Saída:

Cada linha da saída representa uma chamada recursiva. O caractere final impresso em cada linha é um caractere menor que o da linha anterior, e a última linha mostra o 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

Como o Recursivo RevObras ersal passo a passo

O método completo é composto por duas linhas. O caso base, `if (myStr.isEmpty())`, fornece um ponto de parada para a recursão. A linha recursiva, `return reverseString(myStr.substring(1)) + myStr.charAt(0)`, divide o trabalho em duas partes: `substring(1)` retorna tudo o que vem depois do primeiro caractere, e `charAt(0)` retorna esse primeiro caractere, concatenado. depois de o resto invertido.

Tracing a entrada Guru99 deixa a ordem clara. Java Emite um quadro para cada chamada antes que qualquer concatenação ocorra:

A pilha então se desenrola de baixo para cima, e cada quadro anexa seu caractere salvo: a string vazia se torna 9, depois 99, depois 99u, 99ur, 99uru e finalmente 99uruG. Porque Java As strings são imutáveis; nenhum desses valores intermediários sobrescreve o anterior — cada concatenação aloca um novo objeto String.

Dois detalhes na saída do console merecem ser mencionados. A sexta linha termina sem nada após os dois pontos, porque a função substring(1) em uma string de um caractere retorna a string vazia em vez de nula. A mensagem que se segue diz "String in now Empty" no programa original; a frase é um erro de digitação para "String is now empty" e foi mantida para que o código e a saída acima ainda correspondam linha por linha.

Outras maneiras de Reverse uma string em Java

A recursão é a maneira mais clara de veja A reversão acontece, mas raramente da forma como o código de produção a executa. Três alternativas abrangem quase todos os casos reais.

1. StringBuilder.reverse() é a mais curta e a mais rápida. A classe possui um método reverse() integrado, então toda a operação cabe em uma única linha:

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

2. Um laço for com charAt() Percorre a string de trás para frente, do último índice até zero. Os entrevistadores costumam pedir essa versão porque ela demonstra a lógica em vez de delegá-la:

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

3. Uma troca de dois ponteiros para toCharArray() Converte a string em um array de caracteres e, em seguida, troca os caracteres mais externos para os mais internos até que os ponteiros se encontrem no meio:

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

A mesma técnica de matriz inverte uma sequência numérica ou qualquer outra coleção ordenada, razão pela qual ela aparece em Java ordem exercícios com a mesma frequência que nos de cordas.

Complexidade temporal e espacial de cada abordagem

As quatro versões não têm o mesmo custo. Ambas as operações quadráticas abaixo compartilham uma causa: elas criam uma nova string a cada passo, e copiar n caracteres n vezes equivale a um trabalho de n ao quadrado.

Escolha a versão recursiva para aprender ou demonstrar o comportamento da pilha de chamadas, a versão com array de caracteres quando um entrevistador pedir a lógica manualmente e `StringBuilder.reverse()` em qualquer implementação pronta para uso. Essa mesma escolha entre uma solução didática e uma de produção se repete nos exercícios clássicos, desde... Tipo de bolha e Série Fibonacci para verificações de números primos; cada uma delas vale a pena ser praticada em Java de ambas as maneiras.

Perguntas Frequentes