recursion java tutorial with examples
Ten szczegółowy samouczek dotyczący rekursji w języku Java wyjaśnia, czym jest rekursja, z przykładami, typami i pokrewnymi pojęciami. Obejmuje również iterację rekurencji w stosunku do:
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 zachowujemy 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ż iteracyjne podejście do wywołań funkcji.
=> Sprawdź WSZYSTKIE samouczki Java tutaj.
W tym samouczku omówimy inne podejście do programowania, tj. Podejście rekurencyjne.
Czego się nauczysz:
- Co to jest rekursja w Javie?
- Iteracja rekurencyjna kontra w Javie
- Wniosek
Co to jest rekursja w Javie?
Rekurencja to proces, w którym funkcja lub metoda wywołuje siebie wielokrotnie. Ta funkcja, która jest wielokrotnie wywoływana bezpośrednio lub pośrednio, nazywana jest „funkcją rekurencyjną”.
Zobaczymy różne przykłady zrozumienia rekurencji. Zobaczmy teraz składnię rekursji.
Składnia rekursji
Każda metoda implementująca rekursję składa się z dwóch podstawowych części:
- Wywołanie metody, które może wywołać siebie, tj. Rekurencyjnie
- Warunek wstępny, który zatrzyma rekursję.
Zauważ, że warunek wstępny jest konieczny 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 parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Zwróć uwagę, że warunek wstępny jest również nazywany warunkiem podstawowym. Więcej o warunku podstawowym omówimy w następnej sekcji.
Zrozumienie rekurencji w Javie
W tej sekcji postaramy się zrozumieć proces rekursji i zobaczyć, jak to się dzieje. Dowiemy się o warunku podstawowym, przepełnieniu stosu i zobaczymy, jak można rozwiązać konkretny problem za pomocą rekurencji i innych podobnych szczegółów.
Podstawowy warunek 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 podjąć klasyczny problem obliczania silni liczby. Mając liczbę n, musimy znaleźć silnię n oznaczoną przez n!
Teraz zaimplementujmy program do obliczenia silni n (n!) Za pomocą 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); } }Wynik
W tym programie widzimy, że warunek (n<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
W ten sposób możemy stwierdzić, że ostatecznie wartość n będzie 1 lub mniejsza niż 1 iw tym momencie metoda zwróci wartość 1. Ten warunek podstawowy zostanie osiągnięty i funkcja zostanie zatrzymana. Zauważ, że wartość n może być dowolna, o ile spełnia warunek podstawowy.
Rozwiązywanie problemów za pomocą rekursji
Podstawową ideą stosowania rekurencji jest wyrażenie większego problemu w kategoriach mniejszych problemów. Musimy również dodać jeden lub więcej warunków podstawowych, abyśmy mogli wyjść z rekurencji.
Zostało to już zademonstrowane w powyższym przykładzie silni. W tym programie wyraziliśmy silnię n (n!) W postaci mniejszych wartości i mieliśmy warunek bazowy (n<=1) so that when n reaches 1, we can quit the recursive method.
Błąd przepełnienia stosu w rekursji
Zdajemy sobie sprawę, że gdy wywoływana jest jakakolwiek metoda lub funkcja, stan funkcji jest przechowywany na stosie i jest pobierany, gdy funkcja zwraca. Stos jest również używany w metodzie rekurencyjnej.
Ale w przypadku rekurencji problem może wystąpić, jeśli nie zdefiniujemy warunku bazowego lub gdy warunek podstawowy w jakiś sposób nie zostanie 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 silni.
Tutaj podaliśmy zły warunek podstawowy, 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); } }Więc gdy n> 100 metoda zwróci 1, ale rekursja nie zostanie zatrzymana. Wartość n będzie się zmniejszać w nieskończoność, ponieważ nie ma innego warunku, aby ją zatrzymać. Będzie to trwało do momentu przepełnienia stosu.
5 przykładów języków programowania wysokiego poziomu
Innym przypadkiem będzie, gdy wartość n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Przykłady rekurencji w Javie
W tej sekcji zaimplementujemy następujące przykłady przy użyciu rekurencji.
# 1) Szeregi Fibonacciego wykorzystujące rekursję
Szereg Fibonacciego jest określony 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. Również pierwszym elementem szeregu Fibonacciego jest 1.
Więc generalnie, jeśli n jest liczbą bieżącą, to jest to suma (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.
Program do realizacji serii Fibonacciego przedstawiono poniżej:
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 static 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) + ' '); } } } Wynik
# 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 kiedy czytamy ją od lewej do prawej i od prawej do lewej, jest równa. Stąd liczba 121 to palindrom.
Weźmy inną liczbę, 1242. Kiedy czytamy od lewej do prawej, to 1242, a gdy czytamy od prawej do lewej, to 2421. Zatem to nie jest palindrom.
Implementujemy program palindromowy odwracając cyfry liczb i rekurencyjnie porównując podaną liczbę z jej odwróconą reprezentacją.
Poniższy program implementuje program do sprawdzania palindromu.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit 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 { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { 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('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } n = 1221; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } } }Wynik
# 3) Java z odwrotną rekursją ciągów
Biorąc pod uwagę napis „Hello”, musimy go odwrócić, tak aby wynikowy ciąg to „olleH”.
Odbywa się to za pomocą rekurencji. Zaczynając od ostatniego znaku w ciągu, wypisujemy rekurencyjnie każdy znak, aż wszystkie znaki w ciągu zostaną wyczerpane.
Poniższy program używa rekurencji do odwrócenia podanego ciągu.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() <= 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String[] args) { String inputstr = 'SoftwareTestingHelp'; System.out.println('The given string: ' + inputstr); String_Reverse obj = new String_Reverse(); System.out.print('The reversed string: '); obj.reverseString(inputstr); } } Wynik
4) Rekursja Java wyszukiwania binarnego
Algorytm wyszukiwania binarnego to znany algorytm wyszukiwania. W tym algorytmie, mając 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 mid ogranicza nasze wyszukiwanie do pierwszej lub drugiej połowy tablicy. W ten sposób ten sam proces jest powtarzany do momentu znalezienia lokalizacji kluczowych elementów.
Zaimplementujemy ten algorytm przy użyciu rekurencji tutaj.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, 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; //length of the array int 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); } } Wynik
# 5) Znajdź minimalną wartość w tablicy za pomocą rekursji
Korzystając z rekurencji możemy również znaleźć minimalną wartość w tablicy.
Program w języku Java do znalezienia minimalnej wartości w tablicy jest podany poniżej.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //return first element if only one element or minimum of the array elements 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('Minimum element of array: ' + getMin(numArray, 0, n) + '
'); } }Wynik
Oto kilka przykładów rekursji. Oprócz tych przykładów, wiele innych problemów w oprogramowaniu można zaimplementować za pomocą technik rekurencyjnych.
Typy rekurencji
Rekurencja ma dwa typy w zależności od tego, kiedy wywoływana jest metoda rekurencyjna.
Oni są:
jak otworzyć plik swf w programie Adobe Flash Player
1) Rekursja ogona
Gdy wywołanie metody rekurencyjnej jest ostatnią instrukcją wykonywaną wewnątrz metody rekurencyjnej, nazywa się to „Rekursją ogonową”.
W rekurencji ogona rekurencyjna instrukcja call jest zwykle wykonywana razem z instrukcją return metody.
Ogólna składnia rekurencji ogona jest podana poniżej:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) Rekursja głowy
Rekursja głowy to każde podejście rekurencyjne, które nie jest rekurencją ogonową. Więc nawet rekurencja ogólna jest rekursją z wyprzedzeniem.
Składnia rekursji głowy jest następująca:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Iteracja rekurencyjna kontra w Javie
| Rekursja | Iteracja |
|---|---|
| Złożoność czasowa jest bardzo duża. | Złożoność czasowa jest stosunkowo niska. |
| Rekursja to proces, w którym metoda wywołuje się wielokrotnie, aż do spełnienia warunku podstawowego. | Iteracja to proces, w którym fragment kodu jest wykonywany wielokrotnie określoną liczbę razy lub do momentu spełnienia warunku. |
| Czy aplikacja do 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, gdy każde wywołanie rekurencyjne jest wypychane na stos | Używa się stosunkowo mniej pamięci. |
| Trudne do debugowania i utrzymania | Łatwiejsze do debugowania i utrzymania |
| Skutkuje przepełnieniem stosu, jeśli warunek podstawowy nie został określony lub nie został osiągnięty. | Może działać w nieskończoność, ale ostatecznie zatrzyma wykonywanie z jakimikolwiek błędami pamięci |
Często Zadawane Pytania
Pytanie 1) Jak działa rekursja w Javie?
Odpowiedź: W przypadku rekurencji funkcja rekurencyjna wywołuje się wielokrotnie, aż do spełnienia warunku podstawowego. Pamięć dla wywoływanej funkcji jest umieszczana na stosie na górze pamięci dla funkcji wywołującej. Dla każdego wywołania funkcji tworzona jest osobna kopia zmiennych lokalnych.
Pytanie nr 2) Dlaczego używana jest rekursja?
Odpowiedź: Rekursja służy do rozwiązywania 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 w przypadku 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, w przypadku których złożoność czasowa nie jest problemem, użyj rekursji.
Pytanie nr 3) Jakie są zalety rekursji?
Odpowiedź:
Zalety rekursji obejmują:
- Rekurencja redukuje nadmiarowe wywoływanie funkcji.
- Rekursja pozwala nam łatwo rozwiązywać problemy w porównaniu z podejściem iteracyjnym.
P # 4) Który z nich jest lepszy - rekurencja czy iteracja?
Odpowiedź: Rekursja powoduje powtarzające się wywołania, aż do osiągnięcia funkcji podstawowej. W związku z tym istnieje narzut pamięci, ponieważ pamięć dla każdego wywołania funkcji jest wypychana na stos.
Z drugiej strony iteracja nie powoduje dużego obciążenia pamięci. Wykonywanie rekurencji jest wolniejsze niż podejście iteracyjne. Rekursja zmniejsza rozmiar kodu, podczas gdy podejście iteracyjne sprawia, że kod jest duży.
Pytanie nr 5) Jakie są zalety rekursji w porównaniu z iteracją?
Odpowiedź:
- Rekurencja sprawia, że kod jest wyraźniejszy i krótszy.
- Rekursja jest lepsza niż podejście iteracyjne w przypadku problemów takich jak Wieża Hanoi, przechodzenie po drzewach itp.
- Ponieważ każde wywołanie funkcji ma pamięć umieszczoną na stosie, Rekursja zużywa więcej pamięci.
- Wydajność rekurencji jest wolniejsza niż podejście iteracyjne.
Wniosek
Rekursja jest bardzo ważnym pojęciem w oprogramowaniu, niezależnie od języka programowania. Rekurencja jest najczęściej używana w rozwiązywaniu problemów ze strukturą danych, takich jak wieże Hanoi, przechodzenie przez drzewa, połączone listy itp. Chociaż zajmuje więcej pamięci, rekursja sprawia, że kod jest prostszy i bardziej przejrzysty.
W tym samouczku omówiliśmy wszystko na temat rekursji. Wdrożyliśmy również wiele przykładów programowania, aby lepiej zrozumieć koncepcję.
=> Przeczytaj serię szkoleń Easy Java.
rekomendowane lektury
- Rekursja w C ++
- Java Iterator: Naucz się używać iteratorów w Javie z przykładami
- Interfejs ListIterator w Javie z przykładami
- Samouczek JAVA dla początkujących: ponad 100 praktycznych samouczków wideo Java
- Samouczek Java For Loop z przykładami programów
- Java While Loop - samouczek z przykładami programowania
- Java Do While Loop - samouczek z przykładami
- Postrzępiona tablica w Javie - samouczek z przykładami