Ten szczegółowy samouczek na temat rekurencji w Javie wyjaśnia, czym jest rekurencja z przykładami, typami i powiązanymi koncepcjami. Obejmuje również rekurencję w porównaniu z iteracją:
Z naszych wcześniejszych samouczków w Javie widzieliśmy podejście iteracyjne, w którym deklarujemy pętlę, a następnie przechodzimy przez strukturę danych w sposób iteracyjny, biorąc jeden element na raz.
Widzieliśmy również przepływ warunkowy, w którym ponownie przechowujemy jedną zmienną pętli i powtarzamy fragment kodu, aż zmienna pętli spełni warunek. Jeśli chodzi o wywołania funkcji, zbadaliśmy również podejście iteracyjne do wywołań funkcji.
W tym samouczku omówimy inne podejście do programowania, tj. podejście rekursywne.
Czym jest rekurencja w Javie?
Rekursja to proces, w którym funkcja lub metoda wywołuje samą siebie wielokrotnie. Funkcja, która jest wywoływana wielokrotnie bezpośrednio lub pośrednio, nazywana jest "funkcją rekurencyjną".
Zobaczymy różne przykłady, aby zrozumieć rekurencję. Zobaczmy teraz składnię rekurencji.
Składnia rekursji
Każda metoda implementująca rekursję składa się z dwóch podstawowych części:
- Wywołanie metody, która może wywołać samą siebie, tj. rekurencja
- Warunek wstępny, który zatrzyma rekurencję.
Należy pamiętać, że warunek wstępny jest niezbędny dla każdej metody rekurencyjnej, ponieważ jeśli nie przerwiemy rekurencji, będzie ona działać w nieskończoność i spowoduje przepełnienie stosu.
Ogólna składnia rekurencji jest następująca:
methodName (T parametry...) { if (warunek wstępny == true) //warunek wstępny lub warunek podstawowy { return wynik; } return methodName (T parametry...); //wywołanie rekursywne } Należy pamiętać, że warunek wstępny jest również nazywany warunkiem podstawowym. Więcej informacji na temat warunku podstawowego omówimy w następnej sekcji.
Zrozumienie rekurencji w Javie
W tej sekcji postaramy się zrozumieć proces rekurencji i zobaczyć, jak to się odbywa. Dowiemy się o warunku bazowym, przepełnieniu stosu i zobaczymy, jak konkretny problem można rozwiązać za pomocą rekurencji i innych tego typu szczegółów.
Warunek podstawowy rekursji
Pisząc program rekurencyjny, powinniśmy najpierw podać rozwiązanie dla przypadku bazowego. Następnie wyrażamy większy problem w kategoriach mniejszych problemów.
Jako przykład, Możemy wziąć klasyczny problem obliczania czynnika liczby. Biorąc pod uwagę liczbę n, musimy znaleźć czynnik liczby n oznaczony przez n!
Teraz zaimplementujmy program do obliczania współczynnika n (n!) przy użyciu rekurencji.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Wyjście
W tym programie widzimy, że warunek (n<=1) jest warunkiem bazowym i gdy ten warunek zostanie osiągnięty, funkcja zwraca 1. Inna część funkcji jest wywołaniem rekurencyjnym. Ale za każdym razem, gdy wywoływana jest metoda rekurencyjna, n jest zmniejszane o 1.
Możemy zatem stwierdzić, że ostatecznie wartość n wyniesie 1 lub mniej niż 1 i w tym momencie metoda zwróci wartość 1. Ten warunek bazowy zostanie osiągnięty, a funkcja zostanie zatrzymana. Należy pamiętać, że wartość n może być dowolna, o ile spełnia warunek bazowy.
Rozwiązywanie problemów przy użyciu rekursji
Podstawową ideą korzystania z rekurencji jest wyrażenie większego problemu w kategoriach mniejszych problemów. Musimy również dodać jeden lub więcej warunków bazowych, abyśmy mogli wyjść z rekurencji.
Zostało to już zademonstrowane w powyższym przykładzie z czynnikiem. W tym programie wyraziliśmy czynnik n (n!) w kategoriach mniejszych wartości i mieliśmy warunek bazowy (n <=1), więc gdy n osiągnie 1, możemy zakończyć metodę rekursywną.
Błąd przepełnienia stosu w rekurencji
Wiemy, że gdy wywoływana jest dowolna metoda lub funkcja, stan funkcji jest przechowywany na stosie i jest pobierany, gdy funkcja powraca. Stos jest również używany w przypadku metod rekurencyjnych.
Jednak w przypadku rekurencji może wystąpić problem, jeśli nie zdefiniujemy warunku bazowego lub gdy warunek bazowy nie zostanie w jakiś sposób osiągnięty lub wykonany. Jeśli taka sytuacja wystąpi, może dojść do przepełnienia stosu.
Rozważmy poniższy przykład notacji czynnikowej.
Tutaj podaliśmy zły warunek bazowy, n = 100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Tak więc, gdy n> 100 metoda zwróci 1, ale rekurencja nie zostanie zatrzymana. Wartość n będzie nadal zmniejszana w nieskończoność, ponieważ nie ma innego warunku, aby ją zatrzymać. Będzie to trwało aż do przepełnienia stosu.
Innym przypadkiem będzie sytuacja, gdy wartość n <100. W tym przypadku również metoda nigdy nie wykona warunku bazowego i spowoduje przepełnienie stosu.
Przykłady rekurencji w Javie
W tej sekcji zaimplementujemy następujące przykłady przy użyciu rekurencji.
#1) Seria Fibonacciego z wykorzystaniem rekursji
Szereg Fibonacciego jest dany przez,
1,1,2,3,5,8,13,21,34,55,…
Powyższa sekwencja pokazuje, że bieżący element jest sumą dwóch poprzednich elementów. Ponadto pierwszym elementem w ciągu Fibonacciego jest 1.
Ogólnie rzecz biorąc, jeśli n jest bieżącą liczbą, to jest ona dana przez sumę (n-1) i (n-2). Ponieważ bieżący element jest wyrażony w kategoriach poprzednich elementów, możemy wyrazić ten problem za pomocą rekurencji.
Poniżej przedstawiono program implementujący serię Fibonacciego:
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public void main(String[] args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ("Fibonacci Series: First 10 numbers:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Wyjście
#2) Sprawdź czy liczba jest palindromem używając rekursji
Palindrom to sekwencja, która jest równa, gdy czytamy ją od lewej do prawej lub od prawej do lewej.
Biorąc pod uwagę liczbę 121, widzimy, że gdy czytamy ją od lewej do prawej i od prawej do lewej, jest ona równa. Stąd liczba 121 jest palindromem.
Weźmy inną liczbę, 1242. Gdy czytamy ją od lewej do prawej, to 1242, a gdy czytamy ją od prawej do lewej, to 2421. Zatem nie jest to palindrom.
Implementujemy program palindromowy poprzez odwrócenie cyfr liczb i rekurencyjne porównanie danej liczby z jej odwróconą reprezentacją.
Poniższy program implementuje program sprawdzający palindrom.
import java.io.*; import java.util.*; public class Main { // sprawdzenie czy num zawiera tylko jedną cyfrę public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //callfunkcja użytkowa rekurencyjnie revNum = isPalindrome_util(num / 10, revNum); } // Sprawdź, czy pierwsza cyfra num i revNum są równe if (num % 10 == revNum % 10) { // jeśli tak, revNum przesunie się wraz z num return revNum / 10; } else { // exit throw new Exception(); } } //metoda sprawdzania, czy dana liczba jest palindromem przy użyciu funkcji użytkowej palindromu public static int isPalindrome(int num) throwsException { if (num <0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Tak, podana liczba " + n + " jest palindromem."); } catch (Exception e) { System.out.println("Nie, podana liczba " + n + " nie jest palindromem."); } n = 1221; try { isPalindrome(n);System.out.println("Tak, podana liczba " + n + " jest palindromem."); } catch (Wyjątek e) { System.out.println("Nie, podana liczba " + n + " nie jest palindromem."); } } Wyjście
#3) Reverse String Recursion Java
Biorąc pod uwagę ciąg "Hello", musimy odwrócić go tak, aby wynikowy ciąg był "olleH".
Zaczynając od ostatniego znaku w łańcuchu, rekurencyjnie wypisujemy każdy znak, aż do wyczerpania wszystkich znaków w łańcuchu.
Poniższy program wykorzystuje rekurencję do odwrócenia danego ciągu znaków.
class String_Reverse { //rekurencyjna metoda odwracania podanego ciągu void reverseString(String str) { //warunek podstawowy; zwróć, jeśli ciąg ma wartość null lub zawiera 1 lub mniej znaków if ((str==null)} } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Podany ciąg znaków: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Odwrócony ciąg znaków: "); obj.reverseString(inputstr); } } Wyjście
#4) Wyszukiwanie binarne Java Recursion
Algorytm wyszukiwania binarnego jest znanym algorytmem wyszukiwania. W tym algorytmie, biorąc pod uwagę posortowaną tablicę n elementów, przeszukujemy tę tablicę pod kątem danego elementu kluczowego. Na początku dzielimy tablicę na dwie połowy, znajdując środkowy element tablicy.
Następnie, w zależności od tego, czy klucz jest środkowy, ograniczamy wyszukiwanie w pierwszej lub drugiej połowie tablicy. W ten sposób ten sam proces jest powtarzany aż do znalezienia lokalizacji kluczowych elementów.
Zaimplementujemy ten algorytm przy użyciu rekurencji.
import java.util.*; class Binary_Search { // rekurencyjne wyszukiwanie binarne int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //oblicz środek tablicy int mid = left + (right - left) / 2; // jeśli klucz znajduje się na środku, zwróć mid if (numArray[mid] == key) return mid; // jeśli klucz key) return binarySearch(numArray, left, mid - 1, key); // W przeciwnym razie rekurencyjnie przeszukajright subarray return binarySearch(numArray, mid + 1, right, key); } // brak elementów w tablicy, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray[] = { 4,6,12,16,22}; System.out.println("The given array : " + Arrays.toString(numArray)); int len = numArray.length; //długość tablicyint key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " not present"); else System.out.println("Element " + key + " found at index " + result); } } Wyjście
#5) Znajdź minimalną wartość w tablicy przy użyciu rekurencji
Używając rekurencji możemy również znaleźć minimalną wartość w tablicy.
Poniżej przedstawiono program Java do znajdowania minimalnej wartości w tablicy.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //zwraca pierwszy element jeśli tylko jeden element lub minimum elementów tablicy return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Given Array : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Minimalny element tablicy: " + getMin(numArray, 0, n) + "\n"); } } Wyjście
Oprócz tych przykładów, wiele innych problemów w oprogramowaniu może być zaimplementowanych przy użyciu technik rekurencyjnych.
Typy rekursji
Rekursja jest dwojakiego rodzaju, w zależności od tego, kiedy wywoływana jest metoda rekurencyjna.
Są to:
#1) Tail Recursion
Gdy wywołanie metody rekurencyjnej jest ostatnią instrukcją wykonywaną wewnątrz metody rekurencyjnej, nazywa się to "Tail Recursion".
W rekurencji ogonowej rekurencyjna instrukcja wywołania jest zwykle wykonywana wraz z instrukcją powrotu metody.
Ogólna składnia rekurencji ogona jest podana poniżej:
methodName ( T parametry ...){ { if (base_condition == true) { return result; } return methodName (T parametry ...) //tail recursion } #2) Rekursja głowy
Główną rekurencją jest każda rekurencja, która nie jest rekurencją ogonową. Tak więc nawet ogólna rekurencja jest rekurencją wyprzedzającą.
Składnia rekurencji head jest następująca:
methodName (T parametry...){ if (some_condition == true) { return methodName (T parametry...); } return result; } Rekursja a iteracja w Javie
| Rekursja | Iteracja |
|---|---|
| Rekursja to proces, w którym metoda wywołuje samą siebie wielokrotnie, dopóki nie zostanie spełniony podstawowy warunek. | Iteracja to proces, w którym fragment kodu jest wielokrotnie wykonywany przez skończoną liczbę razy lub do momentu spełnienia określonego warunku. |
| Jest to aplikacja dla funkcji. | Ma zastosowanie do pętli. |
| Działa dobrze w przypadku mniejszego rozmiaru kodu. | Działa dobrze w przypadku większego rozmiaru kodu. |
| Wykorzystuje więcej pamięci, ponieważ każde wywołanie rekurencyjne jest wypychane na stos | Wykorzystywana jest stosunkowo mniejsza ilość pamięci. |
| Trudne do debugowania i utrzymania | Łatwiejsze debugowanie i utrzymanie |
| Powoduje przepełnienie stosu, jeśli warunek bazowy nie został określony lub nie został osiągnięty. | Może wykonywać się w nieskończoność, ale ostatecznie zatrzyma wykonywanie w przypadku błędów pamięci. |
| Złożoność czasowa jest bardzo wysoka. | Złożoność czasowa jest stosunkowo niższa. |
Często zadawane pytania
P #1) Jak działa rekurencja w Javie?
Odpowiedź: W rekurencji funkcja rekurencyjna wywołuje samą siebie wielokrotnie, dopóki nie zostanie spełniony warunek podstawowy. Pamięć dla wywoływanej funkcji jest umieszczana na stosie na szczycie pamięci dla funkcji wywołującej. Dla każdego wywołania funkcji tworzona jest osobna kopia zmiennych lokalnych.
Q #2) Dlaczego używana jest rekursja?
Odpowiedź: Rekursja jest używana do rozwiązywania tych problemów, które można podzielić na mniejsze, a cały problem można wyrazić w kategoriach mniejszego problemu.
Rekursja jest również używana do rozwiązywania problemów, które są zbyt złożone, aby można je było rozwiązać za pomocą podejścia iteracyjnego. Oprócz problemów, dla których złożoność czasowa nie jest problemem, należy użyć rekurencji.
Q #3) Jakie są zalety rekursji?
Odpowiedź:
Zalety rekursji obejmują:
- Rekursja redukuje zbędne wywoływanie funkcji.
- Rekursja pozwala nam łatwiej rozwiązywać problemy w porównaniu do podejścia iteracyjnego.
Q #4) Która z tych metod jest lepsza - rekurencja czy iteracja?
Odpowiedź: Rekursja wykonuje powtarzające się wywołania, aż do osiągnięcia funkcji bazowej. W związku z tym występuje narzut pamięci, ponieważ pamięć dla każdego wywołania funkcji jest umieszczana na stosie.
Z drugiej strony iteracja nie ma dużego narzutu na pamięć. Wykonywanie rekurencyjne jest wolniejsze niż podejście iteracyjne. Rekurencja zmniejsza rozmiar kodu, podczas gdy podejście iteracyjne powoduje, że kod jest duży.
Q #5) Jakie są zalety rekurencji w porównaniu z iteracją?
Odpowiedź:
- Rekursja sprawia, że kod jest bardziej przejrzysty i krótszy.
- Rekursja jest lepsza niż podejście iteracyjne w przypadku problemów takich jak Wieża Hanoi, przechodzenie przez drzewa itp.
- Ponieważ każde wywołanie funkcji powoduje przesunięcie pamięci na stos, rekurencja zużywa więcej pamięci.
- Działanie rekurencyjne jest wolniejsze niż podejście iteracyjne.
Wnioski
Rekursja jest bardzo ważną koncepcją w oprogramowaniu, niezależnie od języka programowania. Rekursja jest najczęściej używana w rozwiązywaniu problemów związanych ze strukturą danych, takich jak wieże Hanoi, przechodzenie przez drzewa, połączone listy itp. Chociaż zajmuje więcej pamięci, rekurencja sprawia, że kod jest prostszy i bardziej przejrzysty.
W tym samouczku zbadaliśmy wszystko na temat rekursji. Zaimplementowaliśmy również liczne przykłady programowania, aby lepiej zrozumieć tę koncepcję.