Kaj je rekurzija?
Proces, v katerem funkcija neposredno ali posredno kliče samo sebe, se imenuje rekurzija, ustrezna funkcija pa rekurzivna funkcija. Z uporabo rekurzivnega algoritma je mogoče določene probleme rešiti precej enostavno. Primeri takih težav so Hanojski stolpi (TOH) , Prehodi dreves po vrstnem redu/prednaročilu/po naročilu , DFS grafa itd. Rekurzivna funkcija reši določen problem tako, da pokliče svojo kopijo in reši manjše podprobleme izvirnih problemov. Po potrebi je mogoče ustvariti veliko več rekurzivnih klicev. Bistveno je vedeti, da moramo zagotoviti določen primer, da končamo ta proces rekurzije. Tako lahko rečemo, da vsakič, ko se funkcija pokliče s preprostejšo različico prvotnega problema.
Potreba po rekurziji
Rekurzija je neverjetna tehnika, s pomočjo katere lahko zmanjšamo dolžino naše kode in jo olajšamo za branje in pisanje. Ima določene prednosti pred iteracijsko tehniko, o kateri bomo razpravljali kasneje. Naloga, ki jo je mogoče definirati s podobno podnalogo, je rekurzija ena najboljših rešitev zanjo. Na primer; Faktoriel števila.
Lastnosti rekurzije:
- Večkratno izvajanje istih operacij z različnimi vhodi.
- V vsakem koraku poskušamo z manjšimi vložki, da bi bil problem manjši.
- Za zaustavitev rekurzije je potreben osnovni pogoj, sicer bo prišlo do neskončne zanke.
Algoritem: koraki
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.>
Matematična interpretacija
Vzemimo problem, da mora programer določiti vsoto prvih n naravnih števil, obstaja več načinov za to, vendar je najenostavnejši pristop preprosto sešteti števila, ki se začnejo od 1 do n. Torej je funkcija preprosto videti takole,
pristop (1) – Preprosto dodajanje enega za drugim
f(n) = 1 + 2 + 3 +……..+ n
vendar obstaja še en matematični pristop za predstavitev tega,
pristop(2) – Rekurzivno dodajanje
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
Obstaja preprosta razlika med pristopom (1) in pristopom (2) in to je v pristop (2) funkcijo f( ) sama se kliče znotraj funkcije, zato se ta pojav imenuje rekurzija, funkcija, ki vsebuje rekurzijo, pa se imenuje rekurzivna funkcija, na koncu pa je to odlično orodje v rokah programerjev za kodiranje nekaterih težav na veliko lažji in učinkovit način način.
Kako so rekurzivne funkcije shranjene v pomnilniku?
Rekurzija porabi več pomnilnika, ker rekurzivna funkcija dodaja sklad z vsakim rekurzivnim klicem in tam hrani vrednosti, dokler klic ni končan. Rekurzivna funkcija uporablja strukturo LIFO (ZADNJI PRIŠEL, PRVI ODSTOP) tako kot podatkovna struktura sklada. struktura-sklada-podatkov/
Kaj je osnovni pogoj v rekurziji?
V rekurzivnem programu je zagotovljena rešitev osnovnega primera, rešitev večjega problema pa je izražena z manjšimi problemi.
int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }> V zgornjem primeru je definiran osnovni primer za n <= 1 in večjo vrednost števila je mogoče rešiti s pretvorbo v manjšo, dokler ni dosežen osnovni primer.
Kako se določen problem reši z uporabo rekurzije?
Ideja je predstaviti problem v smislu enega ali več manjših problemov in dodati enega ali več osnovnih pogojev, ki ustavijo rekurzijo. Na primer, faktorial n izračunamo, če poznamo faktorial (n-1). Osnovni primer za faktorial bi bil n = 0. Vrnemo 1, ko je n = 0.
Zakaj pride do napake Stack Overflow pri rekurziji?
Če osnovni primer ni dosežen ali ni definiran, lahko pride do težave s prelivanjem sklada. Vzemimo primer, da to razumemo.
int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }> Če se pokliče fact(10), bo poklical fact(9), fact(8), fact(7) in tako naprej, vendar število ne bo nikoli doseglo 100. Osnovni primer torej ni dosežen. Če te funkcije na skladu izčrpajo pomnilnik, bo to povzročilo napako prekoračitve sklada.
Kakšna je razlika med neposredno in posredno rekurzijo?
Funkcija fun se imenuje neposredno rekurzivna, če kliče isto funkcijo fun. Funkcija fun se imenuje posredna rekurzivna, če kliče drugo funkcijo, recimo fun_new in fun_new kliče fun neposredno ali posredno. Razlika med neposredno in posredno rekurzijo je prikazana v 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... }> Kakšna je razlika med rekurzijo z repom in rekurzijo brez repa?
Rekurzivna funkcija je repno rekurzivna, ko je rekurzivni klic zadnja stvar, ki jo izvede funkcija. Prosimo, glejte članek o repni rekurziji za podrobnosti.
Kako se pomnilnik dodeli različnim klicem funkcij v rekurziji?
Ko je katera koli funkcija poklicana iz main(), se ji dodeli pomnilnik v skladu. Rekurzivna funkcija pokliče samo sebe, pomnilnik za klicano funkcijo se dodeli poleg pomnilnika, dodeljenega klicni funkciji, in za vsak klic funkcije se ustvari drugačna kopija lokalnih spremenljivk. Ko je dosežen osnovni primer, funkcija vrne svojo vrednost funkciji, ki jo je poklicala, pomnilnik pa se sprosti in postopek se nadaljuje.
Vzemimo primer delovanja rekurzije s preprosto funkcijo.
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);> }> |
>
>
Java
enum za niz java
// 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);> > > |
>
>Izhod
3 2 1 1 2 3>
Časovna zapletenost: O(1)
Pomožni prostor: O(1)
Kdaj printFun(3) se kliče iz main(), pomnilnik je dodeljen printFun(3) in preizkus lokalne spremenljivke se inicializira na 3, izjave 1 do 4 pa se potisnejo v sklad, kot je prikazano v spodnjem diagramu. Najprej natisne '3'. V izjavi 2, printFun(2) se pokliče in pomnilnik se dodeli printFun(2) in lokalna spremenljivka test je inicializirana na 2 in izjave 1 do 4 so potisnjene v sklad. Podobno, printFun(2) klice printFun(1) in printFun(1) klice printFun(0) . printFun(0) gre na stavek if in se vrne na printFun(1) . Preostale izjave printFun(1) se izvede in se vrne na printFun(2) in tako naprej. V izhodu se natisnejo vrednosti od 3 do 1 in nato od 1 do 3. Pomnilniški sklad je prikazan na spodnjem diagramu.
Rekurzija VS ponovitev
| Št. SR | Rekurzija | Ponovitev |
| 1) | Konča se, ko osnovni primer postane resničen. | Konča se, ko pogoj postane lažen. |
| 2) | Uporablja se s funkcijami. | Uporablja se z zankami. |
| 3) | Vsak rekurziven klic potrebuje dodaten prostor v pomnilniku sklada. | Vsaka ponovitev ne zahteva dodatnega prostora. |
| 4) | Manjša velikost kode. | Večja velikost kode. |
Zdaj pa razpravljajmo o nekaj praktičnih problemih, ki jih je mogoče rešiti z uporabo rekurzije in razumemo njeno osnovno delovanje. Za osnovno razumevanje preberite naslednje članke.
Osnovno razumevanje rekurzije.
Problem 1: Napišite program in ponovitveno relacijo za iskanje Fibonaccijevega niza od n, kjer je n>2.
Matematična enačba:
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
Relacija ponavljanja:
T(n) = T(n-1) + T(n-2) + O(1)>
Rekurzivni program:
Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
Izvedba:
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
java z razdelitvijo nizov
// 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; }> |
>
>
Java
// 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> |
>
>
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) + ' '); }> |
>
>Izhod
Fibonacci series of 5 numbers is: 0 1 1 2 3>
Časovna zapletenost: O(2n)
Pomožni prostor: O(n)
Tukaj je rekurzivno drevo za vnos 5, ki prikazuje jasno sliko, kako je mogoče velik problem rešiti v manjše.
fib(n) je Fibonaccijeva funkcija. Časovna zahtevnost danega programa je lahko odvisna od klica funkcije.
fib(n) -> raven CBT (UB) -> 2^n-1 vozlišča -> 2^n klic funkcije -> 2^n*O(1) -> T(n) = O(2^n)
Za najboljši primer.
T(n) = ?(2^n2)>
Delo:
Problem 2: Napišite program in relacijo ponavljanja, da poiščete faktoriel od n, kjer je n>2.
Matematična enačba:
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
Relacija ponavljanja:
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
Rekurzivni program:
Vnos: n = 5
Izhod:
faktor 5 je: 120
Izvedba:
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
seznam v polje java
// 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;> }> |
>
>
Java
// 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.> |
>
>
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.> > |
>
>Izhod
factorial of 5 is: 120>
Časovna zahtevnost: O(n)
Pomožni prostor: O(n)
Delo:
Diagram funkcije faktorske rekurzije za uporabniški vnos 5.
Primer: Realne aplikacije rekurzije v realnih problemih
Rekurzija je močna tehnika, ki ima veliko aplikacij v računalništvu in programiranju. Tukaj je nekaj pogostih aplikacij rekurzije:
- Prehod dreves in grafov : Rekurzija se pogosto uporablja za prečkanje in iskanje podatkovnih struktur, kot so drevesa in grafi. Rekurzivne algoritme je mogoče uporabiti za raziskovanje vseh vozlišč ali oglišč drevesa ali grafa na sistematičen način. Algoritmi za razvrščanje : Rekurzivni algoritmi se uporabljajo tudi pri algoritmih za razvrščanje, kot sta hitro razvrščanje in razvrščanje z zlivanjem. Ti algoritmi uporabljajo rekurzijo za razdelitev podatkov v manjše podnize ali podsezname, njihovo razvrščanje in nato ponovno združitev. Algoritmi 'deli in vladaj' : številni algoritmi, ki uporabljajo pristop 'deli in vladaj', kot je algoritem binarnega iskanja, uporabljajo rekurzijo za razčlenitev problema na manjše podprobleme. Generiranje fraktalov: Fraktalne oblike in vzorce je mogoče generirati z uporabo rekurzivnih algoritmov. Na primer, Mandelbrotov niz se ustvari z večkratno uporabo rekurzivne formule za kompleksna števila. Algoritmi za sledenje nazaj : Algoritmi za sledenje nazaj se uporabljajo za reševanje problemov, ki vključujejo sprejemanje zaporedja odločitev, pri čemer je vsaka odločitev odvisna od prejšnjih. Te algoritme je mogoče implementirati z uporabo rekurzije za raziskovanje vseh možnih poti in vrnitev nazaj, ko rešitev ni najdena. Memoizacija : Memoizacija je tehnika, ki vključuje shranjevanje rezultatov dragih funkcijskih klicev in vračanje predpomnjenega rezultata, ko se isti vnosi znova pojavijo. Memoizacijo je mogoče izvesti z uporabo rekurzivnih funkcij za izračun in predpomnilnik rezultatov podproblemov.
To je le nekaj primerov številnih aplikacij rekurzije v računalništvu in programiranju. Rekurzija je vsestransko in močno orodje, ki ga je mogoče uporabiti za reševanje številnih različnih vrst problemov.
Pojasnilo: en pravi primer rekurzije:
Rekurzija je tehnika programiranja, ki vključuje funkcijo, ki kliče samo sebe. Lahko je močno orodje za reševanje zapletenih problemov, vendar zahteva tudi skrbno implementacijo, da se izognete neskončnim zankam in prelivom skladov.
Tukaj je primer izvajanja rekurzije v Pythonu:
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 |
>
>
Java
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
java spletne storitve
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> |
>
>Izhod
120>
V tem primeru definiramo funkcijo, imenovano factorial, ki kot vhod sprejme celo število n. Funkcija uporablja rekurzijo za izračun faktoriala n (tj. produkta vseh pozitivnih celih števil do n).
Funkcija faktorial najprej preveri, ali je n 0 ali 1, kar sta osnovna primera. Če je n 0 ali 1, funkcija vrne 1, saj je 0! in 1! oba sta 1.
Če je n večji od 1, funkcija vstopi v rekurzivni primer. Pokliče sam sebe z n-1 kot argumentom in pomnoži rezultat z n. To izračuna n! z rekurzivnim računanjem (n-1)!.
Pomembno je omeniti, da je rekurzija lahko neučinkovita in povzroči prelivanje skladov, če je ne uporabljate previdno. Vsak klic funkcije doda nov okvir v sklad klicev, kar lahko povzroči preveliko rast sklada, če je rekurzija pregloboka. Poleg tega lahko rekurzija oteži kodo za razumevanje in odpravljanje napak, saj zahteva razmišljanje o več ravneh funkcijskih klicev.
Vendar pa je rekurzija lahko tudi močno orodje za reševanje kompleksnih problemov, zlasti tistih, ki vključujejo razčlenitev problema na manjše podprobleme. Ob pravilni uporabi lahko rekurzija naredi kodo bolj elegantno in lažjo za branje.
Kakšne so slabosti rekurzivnega programiranja pred iterativnim programiranjem?
Upoštevajte, da imajo tako rekurzivni kot iterativni programi enako moč reševanja problemov, tj. vsak rekurzivni program je mogoče napisati iterativno in velja tudi obratno. Rekurzivni program ima večje prostorske zahteve kot iterativni program, saj bodo vse funkcije ostale v skladu, dokler ni dosežen osnovni primer. Prav tako ima večje časovne zahteve zaradi funkcijskih klicev in povratnih stroškov.
Poleg tega so kode zaradi manjše dolžine težko razumljive, zato je pri pisanju kode potrebna posebna previdnost. Računalniku lahko zmanjka pomnilnika, če rekurzivni klici niso pravilno preverjeni.
Kakšne so prednosti rekurzivnega programiranja pred iterativnim programiranjem?
Rekurzija zagotavlja čist in preprost način pisanja kode. Nekatere težave so same po sebi rekurzivne, kot so prehodi dreves, Hanojski stolp , itd. Za takšne težave je bolje napisati rekurzivno kodo. Takšne kode lahko pišemo tudi iterativno s pomočjo podatkovne strukture sklada. Glejte na primer prečkanje neurejenega drevesa brez rekurzije, iterativni hanojski stolp.
Povzetek rekurzije:
- V rekurziji obstajata dve vrsti primerov, tj. rekurzivni primer in osnovni primer.
- Osnovni primer se uporablja za prekinitev rekurzivne funkcije, ko se izkaže, da je primer resničen.
- Vsak rekurziven klic naredi novo kopijo te metode v pomnilniku sklada.
- Neskončna rekurzija lahko povzroči, da zmanjka pomnilnika sklada.
- Primeri rekurzivnih algoritmov: razvrščanje z združitvijo, hitro razvrščanje, Hanojski stolp, Fibonaccijeva serija, faktorski problem itd.
Vadbene težave za začetnike, ki temeljijo na rezultatih:
Vadbena vprašanja za rekurzijo | Komplet 1
Vadbena vprašanja za rekurzijo | Komplet 2
Vadbena vprašanja za rekurzijo | Komplet 3
Vadbena vprašanja za rekurzijo | Komplet 4
Vadbena vprašanja za rekurzijo | Set 5
Vadbena vprašanja za rekurzijo | Komplet 6
Vadbena vprašanja za rekurzijo | Komplet 7
Kviz o rekurziji
Praksa kodiranja na rekurziji:
Vsi članki o rekurziji
Rekurzivne vadbene težave z rešitvami