jak Reverse ciąg w Java za pomocą rekurencji

W tym przykładowym programie odwrócimy ciąg znaków wprowadzony przez użytkownika.

Stworzymy funkcję odwracającą ciąg znaków. Later Będziemy to wywoływać rekurencyjnie, aż wszystkie znaki zostaną odwrócone. Rekurencja sprawdza się w tym problemie, ponieważ odwrócony ciąg to po prostu odwrócony koniec ciągu z oryginalnym pierwszym znakiem doklejonym na końcu, co jest tym samym problemem, ale o jeden znak krótszym.

Napisać Java Program do Reverse sznur

Poniższa klasa deklaruje dane wejściowe w funkcji main(), przekazuje je do funkcji reverseString() i drukuje wynik. Dwa wywołania funkcji println() w metodzie sprawiają, że każdy krok rekurencyjny jest widoczny w konsoli.

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 Wyjście:

Każdy wiersz wyniku to jedno wywołanie rekurencyjne. Ogon wydrukowany w każdym wierszu jest o jeden znak krótszy niż wiersz powyżej, a ostatni wiersz pokazuje odwrócony wynik.

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

Jak rekursywne Reversal Works krok po kroku

Dwie linijki kodu przenoszą całą metodę. Przypadek bazowy, if (myStr.isEmpty()), wskazuje punkt, w którym rekurencja może się zatrzymać. Linia rekurencyjna, return reverseString(myStr.substring(1)) + myStr.charAt(0), dzieli pracę na dwie części: substring(1) to wszystko po pierwszym znaku, a charAt(0) to ten pierwszy znak, do którego dodano po odwrócona reszta.

Tracwejście Guru99 wyjaśnia kolejność. Java przesyła jedną klatkę dla każdego wywołania przed wykonaniem jakiegokolwiek połączenia:

Następnie stos rozwija się od dołu do góry, a każda klatka dodaje zapisany znak: pusty ciąg staje się 9, potem 99, potem 99u, 99ur, 99uru i na końcu 99uruG, Bo Java ciągi znaków są niezmienne, żadna z tych wartości pośrednich nie nadpisuje poprzedniej — każde połączenie przydziela nowy obiekt String.

Warto zwrócić uwagę na dwa szczegóły w wynikach konsoli. Szósty wiersz kończy się pustym wierszem po dwukropku, ponieważ funkcja substring(1) w ciągu jednoznakowym zwraca pusty ciąg zamiast null. Komunikat, który następuje po nim, brzmi „String in now Empty” w oryginalnym programie; to literówka zamiast „String is now empty” i została pozostawiona bez zmian, więc kod i powyższy wynik nadal są zgodne wiersz po wierszu.

Inne sposoby Reverse ciąg w Java

Rekurencja jest najjaśniejszym sposobem widzieć Odwrócenie sytuacji może się zdarzyć, ale rzadko dzieje się tak w kodzie produkcyjnym. Trzy alternatywy obejmują niemal każdy rzeczywisty przypadek.

1. StringBuilder.reverse() jest najkrótsza i najszybsza. Klasa zawiera wbudowaną metodę reverse(), więc całe zadanie mieści się w jednym wierszu:

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

2. Pętla for z charAt() Przechodzi ciąg znaków wstecz od ostatniego indeksu do zera. Ankieterzy często proszą o tę wersję, ponieważ pokazuje ona logikę działania, zamiast ją delegować:

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

3. Zamiana dwóch wskaźników na CharArray() konwertuje ciąg na tablicę znaków, a następnie zamienia skrajne znaki do wewnątrz, aż wskaźniki spotkają się w środku:

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

Ta sama technika tablicowa odwraca sekwencję liczbową lub dowolną inną uporządkowaną kolekcję, dlatego pojawia się w Java szyk ćwiczenia tak często jak w ćwiczeniach smyczkowych.

Złożoność czasowa i przestrzenna każdego podejścia

Cztery wersje nie kosztują tyle samo. Oba poniższe wpisy kwadratowe mają jedną przyczynę: tworzą zupełnie nowy ciąg znaków na każdym kroku, a skopiowanie n znaków n razy to n kwadratów pracy.

Wybierz wersję rekurencyjną, aby się nauczyć lub zademonstrować działanie stosu wywołań, wersję z tablicą znaków, gdy rekruter prosi o logikę ręcznie, oraz StringBuilder.reverse() we wszystkim, co jest dostarczane. Ten sam kompromis między rozwiązaniem dydaktycznym a produkcyjnym pojawia się w klasycznych ćwiczeniach, od… sortowanie bąbelkowe i Seria Fibonacciego do sprawdzanie liczb pierwszych; każdy z nich jest wart ćwiczenia Java w obie strony.

FAQ