Co to jest rekurencja?
Proces, w którym funkcja wywołuje się bezpośrednio lub pośrednio, nazywa się rekurencją, a odpowiadająca jej funkcja nazywa się funkcją rekurencyjną. Stosując algorytm rekurencyjny, niektóre problemy można rozwiązać dość łatwo. Przykładami takich problemów są Wieże Hanoi (TOH) , Przemierzanie drzew w ramach zamówienia/przedsprzedaży/postorderu , DFS of Graph itp. Funkcja rekurencyjna rozwiązuje konkretny problem, wywołując swoją kopię i rozwiązując mniejsze podproblemy pierwotnych problemów. W razie potrzeby można wygenerować wiele innych wywołań rekurencyjnych. Ważne jest, aby wiedzieć, że powinniśmy podać konkretny przypadek, aby zakończyć proces rekurencji. Możemy więc powiedzieć, że za każdym razem, gdy funkcja wywołuje się z prostszą wersją pierwotnego problemu.
Potrzeba rekurencji
Rekurencja to niesamowita technika, za pomocą której możemy zmniejszyć długość naszego kodu i ułatwić jego czytanie i pisanie. Ma pewne zalety w porównaniu z techniką iteracji, które zostaną omówione później. Zadanie, które można zdefiniować za pomocą podobnego podzadania, rekurencja jest dla niego jednym z najlepszych rozwiązań. Na przykład; Silnia liczby.
Właściwości rekurencji:
- Wielokrotne wykonywanie tych samych operacji z różnymi danymi wejściowymi.
- Na każdym kroku staramy się wprowadzać mniejsze dane wejściowe, aby zmniejszyć problem.
- Aby zatrzymać rekurencję, potrzebny jest warunek podstawowy, w przeciwnym razie wystąpi nieskończona pętla.
Algorytm: kroki
The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>
Interpretacja matematyczna
Rozważmy problem polegający na tym, że programista musi wyznaczyć sumę pierwszych n liczb naturalnych. Można to zrobić na kilka sposobów, ale najprostszym podejściem jest po prostu dodanie liczb zaczynających się od 1 do n. Zatem funkcja wygląda po prostu tak,
podejście(1) – Po prostu dodawanie jeden po drugim
f(n) = 1 + 2 + 3 +……..+ n
ale istnieje inne matematyczne podejście do przedstawienia tego,
podejście(2) – Dodawanie rekurencyjne
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
Istnieje prosta różnica między podejściem (1) a podejściem (2). podejście(2) funkcja F( ) samo w sobie jest wywoływane wewnątrz funkcji, więc to zjawisko nazywa się rekurencją, a funkcja zawierająca rekursję nazywa się funkcją rekurencyjną. W końcu jest to świetne narzędzie w rękach programistów do kodowania niektórych problemów w dużo łatwiejszy i wydajniejszy sposób sposób.
W jaki sposób funkcje rekurencyjne są przechowywane w pamięci?
Rekursja zużywa więcej pamięci, ponieważ funkcja rekurencyjna dodaje do stosu przy każdym wywołaniu rekurencyjnym i przechowuje tam wartości aż do zakończenia wywołania. Funkcja rekurencyjna wykorzystuje strukturę LIFO (LAST IN FIRST OUT), podobnie jak struktura danych stosu. struktura-danych stosu/
Jaki jest warunek podstawowy rekurencji?
W programie rekurencyjnym dostarczane jest rozwiązanie przypadku podstawowego, a rozwiązanie większego problemu wyrażane jest w postaci mniejszych problemów.
int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }> W powyższym przykładzie zdefiniowany jest przypadek podstawowy dla n <= 1, a większą wartość liczby można rozwiązać poprzez konwersję na mniejszą, aż do osiągnięcia przypadku podstawowego.
Jak rozwiązuje się konkretny problem za pomocą rekurencji?
Pomysł polega na przedstawieniu problemu w postaci jednego lub większej liczby mniejszych problemów i dodaniu jednego lub większej liczby warunków podstawowych, które zatrzymują rekurencję. Na przykład obliczamy silnię n, jeśli znamy silnię (n-1). Podstawowym przypadkiem silni byłoby n = 0. Zwracamy 1, gdy n = 0.
Dlaczego w rekurencji występuje błąd przepełnienia stosu?
Jeśli przypadek podstawowy nie zostanie osiągnięty lub nie zostanie zdefiniowany, może pojawić się problem przepełnienia stosu. Aby to zrozumieć, weźmy przykład.
int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }> Jeśli zostanie wywołany fakt(10), wywoła fakt(9), fakt(8), fakt(7) i tak dalej, ale liczba nigdy nie osiągnie 100. Zatem przypadek podstawowy nie został osiągnięty. Jeśli pamięć zostanie wyczerpana przez te funkcje na stosie, spowoduje to błąd przepełnienia stosu.
Jaka jest różnica między rekursją bezpośrednią i pośrednią?
Funkcję fun nazywa się bezpośrednią rekurencyjną, jeśli wywołuje tę samą funkcję fun. Funkcję fun nazywa się pośrednią rekurencyjną, jeśli wywołuje inną funkcję, powiedzmy fun_new, a fun_new wywołuje fun bezpośrednio lub pośrednio. Różnicę pomiędzy rekursją bezpośrednią i pośrednią przedstawiono w tabeli 1.
// An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }> Jaka jest różnica między rekurencją ogonową i nieogoniastą?
Funkcja rekurencyjna jest rekurencyjna, gdy wywołanie rekurencyjne jest ostatnią rzeczą wykonywaną przez tę funkcję. Proszę odnieś się artykuł dotyczący rekurencji ogona dla szczegółów.
W jaki sposób pamięć jest przydzielana do różnych wywołań funkcji w rekurencji?
Kiedy jakakolwiek funkcja jest wywoływana z main(), pamięć jest jej przydzielana na stosie. Funkcja rekurencyjna wywołuje samą siebie, pamięć dla wywoływanej funkcji jest przydzielana poza pamięcią przydzieloną funkcji wywołującej i dla każdego wywołania funkcji tworzona jest inna kopia zmiennych lokalnych. Po osiągnięciu przypadku podstawowego funkcja zwraca swoją wartość do funkcji, przez którą została wywołana, pamięć zostaje zwolniona i proces jest kontynuowany.
Weźmy przykład działania rekurencji, biorąc prostą funkcję.
CPP
// A C++ program to demonstrate working of> // recursion> #include> using> namespace> std;> > void> printFun(>int> test)> {> >if> (test <1)> >return>;> >else> {> >cout << test <<>' '>;> >printFun(test - 1);>// statement 2> >cout << test <<>' '>;> >return>;> >}> }> > // Driver Code> int> main()> {> >int> test = 3;> >printFun(test);> }> |
>
>
Jawa
wielowątkowość w Javie
// A Java program to demonstrate working of> // recursion> class> GFG {> >static> void> printFun(>int> test)> >{> >if> (test <>1>)> >return>;> >else> {> >System.out.printf(>'%d '>, test);> >printFun(test ->1>);>// statement 2> >System.out.printf(>'%d '>, test);> >return>;> >}> >}> > >// Driver Code> >public> static> void> main(String[] args)> >{> >int> test =>3>;> >printFun(test);> >}> }> > // This code is contributed by> // Smitha Dinesh Semwal> |
>
>
Python3
# A Python 3 program to> # demonstrate working of> # recursion> > > def> printFun(test):> > >if> (test <>1>):> >return> >else>:> > >print>(test, end>=>' '>)> >printFun(test>->1>)># statement 2> >print>(test, end>=>' '>)> >return> > # Driver Code> test>=> 3> printFun(test)> > # This code is contributed by> # Smitha Dinesh Semwal> |
>
>
C#
// A C# program to demonstrate> // working of recursion> using> System;> > class> GFG {> > >// function to demonstrate> >// working of recursion> >static> void> printFun(>int> test)> >{> >if> (test <1)> >return>;> >else> {> >Console.Write(test +>' '>);> > >// statement 2> >printFun(test - 1);> > >Console.Write(test +>' '>);> >return>;> >}> >}> > >// Driver Code> >public> static> void> Main(String[] args)> >{> >int> test = 3;> >printFun(test);> >}> }> > // This code is contributed by Anshul Aggarwal.> |
>
>
PHP
// PHP program to demonstrate // working of recursion // function to demonstrate // working of recursion function printFun($test) { if ($test <1) return; else { echo('$test '); // statement 2 printFun($test-1); echo('$test '); return; } } // Driver Code $test = 3; printFun($test); // This code is contributed by // Smitha Dinesh Semwal. ?>> |
>
>
JavaScript
> > // JavaScript program to demonstrate working of> // recursion> > function> printFun(test)> >{> >if> (test <1)> >return>;> >else> {> >document.write(test +>' '>);> >printFun(test - 1);>// statement 2> >document.write(test +>' '>);> >return>;> >}> >}> > // Driver code> >let test = 3;> >printFun(test);> > > |
>
>Wyjście
3 2 1 1 2 3>
Złożoność czasowa: O(1)
Przestrzeń pomocnicza: O(1)
Gdy drukujZabawa(3) jest wywoływana z funkcji main(), do której przydzielana jest pamięć drukujZabawa(3) i test zmiennej lokalnej jest inicjowany na 3, a instrukcje od 1 do 4 są umieszczane na stosie, jak pokazano na poniższym schemacie. Najpierw wypisuje „3”. W oświadczeniu 2, drukujZabawa(2) jest wywoływana i przydzielana jest pamięć drukujZabawa(2) i test zmiennej lokalnej jest inicjowany na 2, a instrukcje od 1 do 4 są umieszczane na stosie. Podobnie, drukujZabawa(2) dzwoni drukujZabawa(1) I drukujZabawa(1) dzwoni drukujZabawa(0) . drukujZabawa(0) przechodzi do instrukcji if i powraca do drukujZabawa(1) . Pozostałe wypowiedzi drukujZabawa(1) są wykonywane i powraca do drukujZabawa(2) i tak dalej. Na wyjściu drukowane są wartości od 3 do 1, a następnie od 1 do 3. Stos pamięci pokazano na poniższym schemacie.
Rekurencja vs iteracja
| nr SR | Rekurencja | Iteracja |
| 1) | Kończy się, gdy przypadek podstawowy staje się prawdziwy. | Kończy się, gdy warunek staje się fałszywy. |
| 2) | Używane z funkcjami. | Używany z pętlami. |
| 3) | Każde wywołanie rekurencyjne wymaga dodatkowej przestrzeni w pamięci stosu. | Każda iteracja nie wymaga dodatkowej przestrzeni. |
| 4) | Mniejszy rozmiar kodu. | Większy rozmiar kodu. |
Omówmy teraz kilka praktycznych problemów, które można rozwiązać za pomocą rekurencji i poznajmy jej podstawowe działanie. Aby uzyskać podstawowe informacje, przeczytaj poniższe artykuły.
Podstawowa wiedza na temat rekurencji.
Problem 1: Napisz program i relację powtarzania, aby znaleźć ciąg Fibonacciego n, gdzie n>2.
Równanie matematyczne:
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
Relacja nawrotu:
T(n) = T(n-1) + T(n-2) + O(1)>
Program rekurencyjny:
Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
Realizacja:
C++
// C++ code to implement Fibonacci series> #include> using> namespace> std;> > // Function for fibonacci> > int> fib(>int> n)> > > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >cout<<>'Fibonacci series of 5 numbers is: '>;> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i { cout<' '; } return 0; }> |
>
>
C
// C code to implement Fibonacci series> #include> > // Function for fibonacci> int> fib(>int> n)> > >// Stop condition> >if> (n == 0)> >return> 0;> > >// Stop condition> >if> (n == 1> > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >printf>(>'Fibonacci series '> >'of %d numbers is: '>,> >n);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i printf('%d ', fib(i)); } return 0; }> |
>
>
Jawa
// Java code to implement Fibonacci series> import> java.util.*;> > class> GFG> {> > // Function for fibonacci> static> int> fib(>int> n)> > > // Driver Code> public> static> void> main(String []args)> {> > >// Initialize variable n.> >int> n =>5>;> >System.out.print(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i =>0>; i { System.out.print(fib(i)+' '); } } } // This code is contributed by rutvik_56.> |
>
>
Python3
# Python code to implement Fibonacci series> > # Function for fibonacci> def> fib(n):> > ># Stop condition> >if> (n>=>=> 0>):> >return> 0> > ># Stop condition> >if> (n>=>=> 1> or> n>=>=> 2>):> >return> 1> > ># Recursion function> >else>:> >return> (fib(n>-> 1>)>+> fib(n>-> 2>))> > > # Driver Code> > # Initialize variable n.> n>=> 5>;> print>(>'Fibonacci series of 5 numbers is :'>,end>=>' '>)> > # for loop to print the fibonacci series.> for> i>in> range>(>0>,n):> >print>(fib(i),end>=>' '>)> |
>
>
C#
using> System;> > public> class> GFG> {> > >// Function for fibonacci> >static> int> fib(>int> n)> > n == 2)> >return> 1;> > >// Recursion function> >else> >return> (fib(n - 1) + fib(n - 2));> >> > >// Driver Code> >static> public> void> Main ()> >{> > >// Initialize variable n.> >int> n = 5;> >Console.Write(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i { Console.Write(fib(i) + ' '); } } } // This code is contributed by avanitrachhadiya2155> |
inaczej Java
>
>
JavaScript
> // JavaScript code to implement Fibonacci series> > // Function for fibonacci> function> fib(n)> n == 2)> >return> 1;> >// Recursion function> >else> >return> fib(n-1) + fib(n-2);> > > // Initialize variable n.> let n = 5;> > document.write(>'Fibonacci series of 5 numbers is: '>);> > // for loop to print the fibonacci series.> for>(let i = 0; i { document.write(fib(i) + ' '); }> |
>
>Wyjście
Fibonacci series of 5 numbers is: 0 1 1 2 3>
Złożoność czasowa: O(2N)
Przestrzeń pomocnicza: NA)
Oto drzewo rekurencyjne dla wejścia 5, które pokazuje jasny obraz tego, jak duży problem można rozwiązać na mniejsze.
fib(n) jest funkcją Fibonacciego. Złożoność czasowa danego programu może zależeć od wywołania funkcji.
fib(n) -> poziom CBT (UB) -> 2^n-1 węzły -> 2^n wywołanie funkcji -> 2^n*O(1) -> T(n) = O(2^n)
Najlepszy przypadek.
T(n) = ?(2^n2)>
Pracujący:
Problem 2: Napisz program i relację powtarzania, aby znaleźć silnię n, gdzie n>2.
Równanie matematyczne:
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
Relacja nawrotu:
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
Program rekurencyjny:
Wejście: n = 5
Wyjście:
silnia liczby 5 wynosi: 120
Realizacja:
C++
// C++ code to implement factorial> #include> using> namespace> std;> > // Factorial function> int> f(>int> n)> n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> > > // Driver code> int> main()> {> >int> n = 5;> >cout<<>'factorial of '><' is: '< return 0; }> |
>
>
C
// C code to implement factorial> #include> > // Factorial function> int> f(>int> n)> > >// Stop condition> >if> (n == 0> > // Driver code> int> main()> {> >int> n = 5;> >printf>(>'factorial of %d is: %d'>, n, f(n));> >return> 0;> }> |
>
>
Jawa
// Java code to implement factorial> public> class> GFG> {> > >// Factorial function> >static> int> f(>int> n)> >> > >// Driver code> >public> static> void> main(String[] args)> >{> >int> n =>5>;> >System.out.println(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyesh072019.> |
>
>
Python3
# Python3 code to implement factorial> > # Factorial function> def> f(n):> > ># Stop condition> >if> (n>=>=> 0> or> n>=>=> 1>):> >return> 1>;> > ># Recursive condition> >else>:> >return> n>*> f(n>-> 1>);> > > # Driver code> if> __name__>=>=>'__main__'>:> > >n>=> 5>;> >print>(>'factorial of'>,n,>'is:'>,f(n))> > ># This code is contributed by pratham76.> |
>
>
C#
// C# code to implement factorial> using> System;> class> GFG {> > >// Factorial function> >static> int> f(>int> n)> > n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> >> > >// Driver code> >static> void> Main()> >{> >int> n = 5;> >Console.WriteLine(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyeshrabadiya07.> |
>
napisz json do pliku python
>
JavaScript
> // JavaScript code to implement factorial> > // Factorial function> function> f(n)> n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n*f(n-1);> > > // Initialize variable n.> let n = 5;> document.write(>'factorial of '>+ n +>' is: '> + f(n));> > // This code is contributed by probinsah.> > |
>
>Wyjście
factorial of 5 is: 120>
Złożoność czasowa: NA)
Przestrzeń pomocnicza: NA)
Pracujący:
Schemat silniowej funkcji rekurencji dla danych wejściowych użytkownika 5.
Przykład: Rzeczywiste zastosowania rekurencji w rzeczywistych problemach
Rekurencja to potężna technika, która ma wiele zastosowań w informatyce i programowaniu. Oto niektóre z typowych zastosowań rekurencji:
- Przechodzenie przez drzewa i wykresy: Rekurencja jest często używana do przechodzenia i przeszukiwania struktur danych, takich jak drzewa i wykresy. Algorytmy rekurencyjne można wykorzystać do systematycznego eksplorowania wszystkich węzłów lub wierzchołków drzewa lub wykresu. Algorytmy sortowania: Algorytmy rekurencyjne są również używane w algorytmach sortowania, takich jak sortowanie szybkie i sortowanie przez scalanie. Algorytmy te wykorzystują rekurencję do dzielenia danych na mniejsze podtablice lub listy podrzędne, sortowania ich, a następnie ponownego łączenia. Algorytmy „dziel i zwyciężaj”: wiele algorytmów korzystających z podejścia „dziel i zwyciężaj”, takich jak algorytm wyszukiwania binarnego, wykorzystuje rekurencję do podziału problemu na mniejsze podproblemy. Generowanie fraktali: kształty i wzory fraktali można generować za pomocą algorytmów rekurencyjnych. Na przykład zbiór Mandelbrota jest generowany poprzez wielokrotne stosowanie formuły rekurencyjnej do liczb zespolonych. Algorytmy wycofywania się: Algorytmy wycofywania służą do rozwiązywania problemów polegających na podejmowaniu sekwencji decyzji, gdzie każda decyzja zależy od poprzednich. Algorytmy te można zaimplementować przy użyciu rekurencji w celu zbadania wszystkich możliwych ścieżek i cofnięcia się, gdy nie zostanie znalezione rozwiązanie. Zapamiętywanie: Zapamiętywanie to technika polegająca na przechowywaniu wyników kosztownych wywołań funkcji i zwracaniu wyników z pamięci podręcznej, gdy ponownie pojawią się te same dane wejściowe. Zapamiętywanie można wdrożyć za pomocą funkcji rekurencyjnych do obliczania i buforowania wyników podproblemów.
To tylko kilka przykładów wielu zastosowań rekurencji w informatyce i programowaniu. Rekurencja jest wszechstronnym i potężnym narzędziem, które można wykorzystać do rozwiązania wielu różnych typów problemów.
Wyjaśnienie: jeden prawdziwy przykład rekurencji:
Rekurencja to technika programowania polegająca na wywołaniu funkcji. Może to być potężne narzędzie do rozwiązywania złożonych problemów, ale wymaga również starannej implementacji, aby uniknąć nieskończonych pętli i przepełnienia stosu.
Oto przykład implementacji rekurencji w Pythonie:
C++
#include> using> namespace> std;> int> factorial(>int> n)> {> > >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > int> main()> {> > >// Call the factorial function and print the result> >int> result = factorial(5);> >cout << result |
>
>
Jawa
import> java.util.*;> > class> Main {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n ==>0> || n ==>1>) {> >return> 1>;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n ->1>);> >}> >}> > >public> static> void> main(String[] args)> >{> >// Call the factorial function and print the result> >int> result = factorial(>5>);> >System.out.println(result);>// Output: 120> >}> }> |
>
>
Python3
def> factorial(n):> ># Base case: if n is 0 or 1, return 1> >if> n>=>=> 0> or> n>=>=> 1>:> >return> 1> > ># Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else>:> >return> n>*> factorial(n>->1>)> > # Call the factorial function and print the result> result>=> factorial(>5>)> print>(result)># Output: 120> |
>
>
C#
using> System;> > class> MainClass {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> >}> > >public> static> void> Main (>string>[] args) {> >// Call the factorial function and print the result> >int> result = factorial(5);> >Console.WriteLine(result);>// Output: 120> >}> }> |
>
>
JavaScript
function> factorial(n) {> >// Base case: if n is 0 or 1, return 1> >if> (n === 0 || n === 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > // Call the factorial function and print the result> const result = factorial(5);> console.log(result);>// Output: 120> |
>
>Wyjście
120>
W tym przykładzie definiujemy funkcję zwaną silnią, która jako dane wejściowe przyjmuje liczbę całkowitą n. Funkcja używa rekurencji do obliczenia silni n (tj. iloczynu wszystkich dodatnich liczb całkowitych aż do n).
Funkcja silni najpierw sprawdza, czy n wynosi 0 czy 1, co jest przypadkiem podstawowym. Jeśli n wynosi 0 lub 1, funkcja zwraca 1, ponieważ 0! i 1! oba są 1.
Jeśli n jest większe niż 1, funkcja przechodzi w przypadek rekurencyjny. Wywołuje się z argumentem n-1 i mnoży wynik przez n. To oblicza n! poprzez rekurencyjne obliczanie (n-1)!.
Należy pamiętać, że rekurencja może być nieefektywna i prowadzić do przepełnienia stosu, jeśli nie jest stosowana ostrożnie. Każde wywołanie funkcji dodaje nową ramkę do stosu wywołań, co może spowodować, że stos stanie się zbyt duży, jeśli rekursja będzie zbyt głęboka. Ponadto rekurencja może sprawić, że kod będzie trudniejszy do zrozumienia i debugowania, ponieważ wymaga myślenia o wielu poziomach wywołań funkcji.
Jednak rekurencja może być również potężnym narzędziem do rozwiązywania złożonych problemów, szczególnie tych, które wymagają podziału problemu na mniejsze podproblemy. Przy prawidłowym użyciu rekurencja może sprawić, że kod będzie bardziej elegancki i łatwiejszy do odczytania.
Jakie są wady programowania rekurencyjnego w porównaniu z programowaniem iteracyjnym?
Należy zauważyć, że zarówno programy rekurencyjne, jak i iteracyjne mają tę samą zdolność rozwiązywania problemów, tj. każdy program rekurencyjny można napisać iteracyjnie i odwrotnie, jest to również prawdą. Program rekurencyjny ma większe wymagania przestrzenne niż program iteracyjny, ponieważ wszystkie funkcje pozostaną na stosie, aż do osiągnięcia przypadku podstawowego. Ma również większe wymagania czasowe ze względu na wywołania funkcji i narzut związany ze zwrotami.
Co więcej, ze względu na mniejszą długość kodu, kody są trudne do zrozumienia, dlatego podczas pisania kodu należy zachować szczególną ostrożność. W komputerze może zabraknąć pamięci, jeśli wywołania rekurencyjne nie zostaną prawidłowo sprawdzone.
Jakie są zalety programowania rekurencyjnego w porównaniu z programowaniem iteracyjnym?
Rekurencja zapewnia czysty i prosty sposób pisania kodu. Niektóre problemy są z natury rekurencyjne, jak przechodzenie przez drzewo, Wieża Hanoi itp. W przypadku takich problemów preferowane jest pisanie kodu rekurencyjnego. Takie kody możemy pisać także iteracyjnie za pomocą struktury danych stosu. Na przykład zobacz Inorder Tree Traversal Without Recursion, Iterative Tower of Hanoi.
Linux $home
Podsumowanie rekurencji:
- W rekurencji występują dwa typy przypadków, tj. przypadek rekurencyjny i przypadek podstawowy.
- Przypadek podstawowy służy do zakończenia funkcji rekurencyjnej, gdy przypadek okaże się prawdziwy.
- Każde wywołanie rekurencyjne tworzy nową kopię tej metody w pamięci stosu.
- Nieskończona rekurencja może prowadzić do wyczerpania pamięci stosu.
- Przykłady algorytmów rekurencyjnych: sortowanie przez scalanie, sortowanie szybkie, wieża Hanoi, szereg Fibonacciego, problem silniowy itp.
Praktyczne problemy oparte na wynikach dla początkujących:
Ćwicz pytania dotyczące rekurencji | Zestaw 1
Ćwicz pytania dotyczące rekurencji | Zestaw 2
Ćwicz pytania dotyczące rekurencji | Zestaw 3
Ćwicz pytania dotyczące rekurencji | Zestaw 4
Ćwicz pytania dotyczące rekurencji | Zestaw 5
Ćwicz pytania dotyczące rekurencji | Zestaw 6
Ćwicz pytania dotyczące rekurencji | Zestaw 7
Quiz na temat rekurencji
Praktyka kodowania w przypadku rekurencji:
Wszystkie artykuły na temat rekurencji
Rekurencyjne problemy praktyczne z rozwiązaniami