Wprowadzenie do funkcji rekurencyjnej w Javie
Funkcja rekurencyjna to taka, która wywołuje się jeden lub wiele razy. Funkcja rekurencyjna jest używana w sytuacjach, w których ten sam zestaw operacji musi być wykonywany wielokrotnie, aż do osiągnięcia wyniku. Wykonuje kilka iteracji, a opis problemu staje się coraz prostszy z każdą iteracją.
Zawsze należy określić limit podstawowy podczas pisania funkcji rekurencyjnej, w przeciwnym razie spowoduje to błąd przepełnienia stosu. Stos to obszar pamięci zarezerwowany do obsługi wywołań metod. Błąd wynika z faktu, że funkcja zaczyna działać w sposób ciągły, ponieważ nie będzie w stanie znaleźć warunku granicznego, a zatem w końcu wyczerpie przydzieloną pamięć. Aby zapobiec przepełnieniu stosu, definiujemy określone warunki podstawowe za pomocą instrukcji „if… else” (lub dowolnych innych instrukcji warunkowych), które powodują zatrzymanie funkcji rekurencji po zakończeniu wymaganego obliczenia.
Rodzaje rekurencji w Javie
Istnieją 2 rodzaje rekurencji w Javie. Oni są:
1. Bezpośrednia rekurencja
Składnia:
Tutaj funkcja 1 wywołuje się ciągle, dlatego jest funkcją rekurencyjną.
public static void main(String() args)(
//few lines of code
function();
//few lines of code
)
function() (
//few lines of code
function();
//few lines of code
)
Przykład
Wieloczynnik liczby jest przykładem bezpośredniej rekurencji. Podstawową zasadą rekurencji jest rozwiązanie złożonego problemu przez podział na mniejsze. Na przykład w przypadku silni liczby obliczamy silnię „i”, jeśli znamy jej silnię „i-1”.
Kod:
public class Factorial (
static int fact(int i)(
if (i == 1)
return 1;
else
return(i * fact(i-1));
)
public static void main(String() args) (
System.out.println("The factorial of given number 6 is: "+fact(6));
)
)
Wynik:
2. Pośrednia / wzajemna rekurencja
Funkcja 1, która wywołuje inną funkcję2, która z kolei wywołuje funkcję 1 bezpośrednio lub pośrednio, nazywa się pośrednią funkcją rekurencyjną.
Składnia:
Rozważ 2 funkcje o nazwie function1 () i function2 (). Tutaj funkcja 1 wywołuje funkcję 2, a funkcja 2 wywołuje funkcję 1.
function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)
Przykład
Aby pokazać pośrednią rekurencję, bierzemy następujący program służący do sprawdzenia, czy podana liczba jest parzysta czy nieparzysta.
Kod:
import java.util.Scanner;
public class IndirectRecursion (
public static boolean oddNum(int i) (
if (i<0) throw new IllegalArgumentException("Number is negative");
if(i == 0)(
return false;
) else (
return evenNum(i-1);
)
)
public static boolean evenNum(int i) (
if (i<0) throw new IllegalArgumentException("Number is negative");
if(i == 0)(
return true;
) else (
return oddNum(i-1);
)
)
public static void main(String() args) (
Scanner inputNum = new Scanner(System.in);
System.out.print("Give a number: ");
int n = inputNum.nextInt();
if (evenNum(n)) System.out.println(n + " is even");
else System.out.println(n + " is odd");
inputNum.close();
)
)
Wynik:
Przykłady rekurencji w Javie
Oto kilka przykładów rozwiązywania problemów za pomocą metody rekurencji.
Przykład 1 - Sekwencja Fibonacciego
Mówi się, że zbiór liczb „n” jest w sekwencji Fibonacciego, jeśli liczba 3 = liczba 1 + liczba 2, tj. Każda liczba jest sumą dwóch poprzednich liczb. Dlatego sekwencja zawsze zaczyna się od pierwszych dwóch cyfr, takich jak 0 i 1. Trzecia cyfra to suma 0 i 1, co daje 1, czwarta liczba to dodanie 1 i 1, co daje 2, a sekwencja trwa.
Sprawdź następujący kod w Javie, aby wygenerować sekwencję Fibonacciego:
public class FibonacciSeries(
static int num1=0, num2=1, num3=0;
static void fibonacci(int n)(
if(n>0)(
num3 = num1 + num2;
num1 = num2;
num2 = num3;
System.out.print(" "+num3);
fibonacci(n-1);
)
)
public static void main(String args())(
int n=10;
System.out.print(num1+" "+num2);//printing constant first two digits 0 and 1
fibonacci(n-2);//Since first two numbers are already done
)
)
Wynik:
Tutaj pierwsze dwie liczby są inicjowane na 0 i 1 i drukowane. Zmienne „num1”, „num2” i „num3” służą do wygenerowania wymaganej sekwencji. Zmienna „num3” jest uzyskiwana przez dodanie „num1” i „num2”, a liczby są przesuwane o jedną pozycję w lewo przez tasowanie, jak pokazano w kodzie. Funkcja „Fibonacciego” jest tutaj wywoływana rekurencyjnie i przy każdej iteracji wartość „n” zmniejsza się o 1. Stąd rekursja kończy się, gdy tylko „n” osiągnie wartość 0.
Przykład # 2 - Wieża Hanoi
Jest to klasyczny problem matematyczny, który ma 3 bieguny i liczbę „n” dysków o różnych rozmiarach. Układanka wygląda następująco:
Na początku w pierwszym biegunie dyski będą ustawione tak, aby największy z nich znajdował się na dole, a najmniejszy na szczycie bieguna. Celem jest przeniesienie tych dysków z pierwszego bieguna na trzeci biegun, utrzymując dyski w tej samej pozycji, co w pierwszym biegunie. Podczas przenoszenia tych dysków należy pamiętać o kilku warunkach:
1. Jednocześnie należy przenieść tylko jeden dysk.
2. W trakcie tego procesu umieszczanie większego dysku na mniejszym nie jest dozwolone.
3. Drugi (środkowy) biegun może służyć do pośredniczenia podczas przenoszenia dysków z pierwszego na drugi biegun.
Poniżej znajduje się kod Java, którego można użyć do rozwiązania zagadki:
Kod:
public class TowerOfHanoi (
public static void main(String() args) (
int count = 3;
tower(count, 'A', 'B', 'C');
)
public static void tower(int first, char disk1, char temp, char disk2) (
if (first == 1) (
System.out.println("Disk 1 from " + disk1 + " to " + disk2);
) else (
tower(first - 1, disk1, disk2, temp);
System.out.println("Disk " + first + " from " + disk1 + " to " + disk2);
tower(first - 1, temp, disk1, disk2);
)
)
)
Wynik:
W tym przypadku zmienna „liczba” reprezentuje liczbę używanych dysków. Funkcja „wieża” to funkcja rekurencyjna używana do przenoszenia dysków z pręta 1 na pręt 3. Proste rozwiązanie tego problemu można uzyskać, biorąc pod uwagę 2 dyski na początku.
- Najpierw zaczynamy od przeniesienia dysku 1 z pręta 1 na pręt 2.
- Następnie przenosimy dysk 2 na pręt 3.
- Na koniec kończymy przenoszeniem dysku 1 na pręt 3, uzupełniając wymagane rozwiązanie.
Tę samą zasadę stosuje się do liczby „n” dysków, przenosząc (n-1) tarczę z pręta 1 na 2 i wykonując podobne kroki jak powyżej.
Zalety rekurencji w Javie
- Kod jest łatwy do napisania i utrzymania.
- Najlepsza metoda na znalezienie wyników, w których wymagana jest duża liczba iteracji.
Wady rekurencji w Javie
- Funkcje rekurencyjne zużywają więcej pamięci. Jest tak, ponieważ za każdym razem, gdy wywoływana jest funkcja rekurencyjna; alokacja pamięci jest wykonywana na nowo dla zmiennych na stosie. Odpowiedni przydział pamięci jest zwalniany, gdy tylko zwracane są wartości zmiennych.
- Ten proces alokacji pamięci zajmuje więcej czasu, dlatego wykonanie jest zwykle powolne.
Wniosek
Funkcje rekurencyjne są stosunkowo prostsze w kodowaniu, ale nie są również tak wydajne w porównaniu do innych istniejących metod. Dlatego są one głównie stosowane w przypadkach, w których czas przeznaczony na rozwój jest krótszy, a także w przypadku, gdy w problemie można zaobserwować znaczny wzór.
Polecane artykuły
To jest przewodnik po rekursji w Javie. Tutaj omawiamy rodzaje Rekurencji w Javie wraz z jej różnymi przykładami z zaletami i wadami. Możesz także przejrzeć następujące artykuły, aby dowiedzieć się więcej-
- JScrollPane w Javie
- Funkcje matematyczne w Javie
- Funkcje matematyczne w Javie
- Konstruktor w Javie
- Funkcja rekurencyjna w Pythonie
- Program czynnikowy w JavaScript