Wat is recursie?
Het proces waarbij een functie zichzelf direct of indirect aanroept, wordt recursie genoemd en de overeenkomstige functie wordt een recursieve functie genoemd. Met behulp van een recursief algoritme kunnen bepaalde problemen vrij eenvoudig worden opgelost. Voorbeelden van dergelijke problemen zijn Torens van Hanoi (TOH) , Inorder/Preorder/Postorder Tree Traversals , DFS of Graph , enz. Een recursieve functie lost een bepaald probleem op door een kopie van zichzelf aan te roepen en kleinere deelproblemen van de oorspronkelijke problemen op te lossen. Er kunnen veel meer recursieve oproepen worden gegenereerd wanneer dat nodig is. Het is essentieel om te weten dat we een bepaald geval moeten opgeven om dit recursieproces te beëindigen. We kunnen dus zeggen dat de functie zichzelf elke keer aanroept met een eenvoudigere versie van het oorspronkelijke probleem.
Behoefte aan recursie
Recursie is een verbazingwekkende techniek waarmee we de lengte van onze code kunnen verkorten en het lezen en schrijven gemakkelijker kunnen maken. Het heeft bepaalde voordelen ten opzichte van de iteratietechniek die later zullen worden besproken. Een taak die kan worden gedefinieerd met zijn vergelijkbare subtaak, recursie is daarvoor een van de beste oplossingen. Bijvoorbeeld; De faculteit van een getal.
Eigenschappen van recursie:
- Het meerdere keren uitvoeren van dezelfde bewerkingen met verschillende ingangen.
- Bij elke stap proberen we kleinere inputs om het probleem kleiner te maken.
- De basisvoorwaarde is nodig om de recursie te stoppen, anders zal er een oneindige lus optreden.
Algoritme: stappen
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.>
Een wiskundige interpretatie
Laten we eens kijken naar het probleem dat een programmeur de som van de eerste n natuurlijke getallen moet bepalen. Er zijn verschillende manieren om dat te doen, maar de eenvoudigste aanpak is simpelweg het optellen van de getallen vanaf 1 tot n. De functie ziet er dus eenvoudigweg zo uit:
approach(1) – Gewoon één voor één toevoegen
f(n) = 1 + 2 + 3 +……..+ n
maar er is een andere wiskundige benadering om dit weer te geven,
approach(2) – Recursief optellen
f(n) = 1n=1
f(n) = n + f(n-1) n>1
Er is een eenvoudig verschil tussen de aanpak (1) en de aanpak (2), en dat zit erin aanpak(2) de functie F( ) zelf wordt binnen de functie aangeroepen, dus dit fenomeen wordt recursie genoemd, en de functie die recursie bevat, wordt recursieve functie genoemd. Uiteindelijk is dit een geweldig hulpmiddel in de hand van programmeurs om sommige problemen veel eenvoudiger en efficiënter te coderen manier.
Hoe worden recursieve functies in het geheugen opgeslagen?
Recursie gebruikt meer geheugen, omdat de recursieve functie bij elke recursieve aanroep de stapel aanvult en de waarden daar bewaart totdat de aanroep is voltooid. De recursieve functie gebruikt de LIFO-structuur (LAST IN FIRST OUT), net als de stapelgegevensstructuur. stapel-data-structuur/
Wat is de basisvoorwaarde bij recursie?
In het recursieve programma wordt de oplossing voor het basisscenario gegeven en wordt de oplossing voor het grotere probleem uitgedrukt in termen van kleinere problemen.
int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }> In het bovenstaande voorbeeld is het basisscenario voor n <= 1 gedefinieerd en kan de grotere waarde van een getal worden opgelost door deze naar een kleiner getal te converteren totdat het basisscenario is bereikt.
Hoe wordt een bepaald probleem opgelost met behulp van recursie?
Het idee is om een probleem weer te geven in termen van een of meer kleinere problemen, en een of meer basisvoorwaarden toe te voegen die de recursie stoppen. We berekenen bijvoorbeeld faculteit n als we de faculteit van (n-1) kennen. Het basisscenario voor faculteit zou n = 0 zijn. We retourneren 1 als n = 0.
Waarom treedt er een Stack Overflow-fout op bij recursie?
Als het basisscenario niet wordt bereikt of niet gedefinieerd, kan het stack-overflow-probleem optreden. Laten we een voorbeeld nemen om dit te begrijpen.
int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }> Als feit(10) wordt aangeroepen, wordt feit(9), feit(8), feit(7), enzovoort aangeroepen, maar het getal zal nooit 100 bereiken. Het basisscenario wordt dus niet bereikt. Als het geheugen door deze functies op de stapel uitgeput raakt, zal dit een stapeloverloopfout veroorzaken.
Wat is het verschil tussen directe en indirecte recursie?
Een functie fun wordt direct recursief genoemd als deze dezelfde functie fun aanroept. Een functie fun wordt indirect recursief genoemd als deze een andere functie aanroept, bijvoorbeeld fun_new, en fun_new roept direct of indirect fun op. Het verschil tussen directe en indirecte recursie wordt geïllustreerd in Tabel 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... }> Wat is het verschil tussen staart- en niet-staartrecursie?
Een recursieve functie is staartrecursief wanneer een recursieve aanroep het laatste is dat door de functie wordt uitgevoerd. Raadpleeg alstublieft staartrecursie artikel voor details.
Hoe wordt geheugen toegewezen aan verschillende functieaanroepen in recursie?
Wanneer een functie vanuit main() wordt aangeroepen, wordt het geheugen daaraan op de stapel toegewezen. Een recursieve functie roept zichzelf aan, het geheugen voor een opgeroepen functie wordt toegewezen bovenop het geheugen dat is toegewezen aan de aanroepende functie en voor elke functieaanroep wordt een andere kopie van lokale variabelen gemaakt. Wanneer het basisscenario wordt bereikt, retourneert de functie zijn waarde aan de functie door wie deze wordt aangeroepen, wordt de toewijzing van geheugen ongedaan gemaakt en gaat het proces verder.
Laten we het voorbeeld nemen van hoe recursie werkt door een eenvoudige functie te nemen.
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
java hallo wereld voorbeeld
// 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);> > > |
>
>Uitvoer
3 2 1 1 2 3>
Tijdcomplexiteit: O(1)
Hulpruimte: O(1)
Wanneer printFun(3) wordt aangeroepen vanuit main(), waaraan geheugen wordt toegewezen printFun(3) en een lokale variabeletest wordt geïnitialiseerd op 3 en verklaringen 1 tot en met 4 worden op de stapel geduwd, zoals weergegeven in het onderstaande diagram. Er wordt eerst ‘3’ afgedrukt. In verklaring 2, printFun(2) wordt aangeroepen en waaraan geheugen wordt toegewezen printFun(2) en een lokale variabeletest wordt geïnitialiseerd op 2 en verklaringen 1 tot en met 4 worden in de stapel geduwd. Op dezelfde manier, printFun(2) oproepen printFun(1) En printFun(1) oproepen printFun(0) . printFun(0) gaat naar de if-instructie en keert terug naar printFun(1) . De resterende verklaringen van printFun(1) worden uitgevoerd en het keert terug naar printFun(2) enzovoort. In de uitvoer worden waarden van 3 tot 1 afgedrukt en vervolgens 1 tot 3. De geheugenstapel is weergegeven in het onderstaande diagram.
Recursie versus iteratie
| Sorry. Nee. | Herhaling | Iteratie |
| 1) | Eindigt wanneer het basisscenario waar wordt. | Beëindigt wanneer de voorwaarde onwaar wordt. |
| 2) | Gebruikt met functies. | Gebruikt met lussen. |
| 3) | Elke recursieve oproep heeft extra ruimte in het stapelgeheugen nodig. | Elke iteratie vereist geen extra ruimte. |
| 4) | Kleinere codegrootte. | Grotere codegrootte. |
Laten we nu een paar praktische problemen bespreken die kunnen worden opgelost door recursie te gebruiken en de basiswerking ervan te begrijpen. Voor basiskennis kunt u de volgende artikelen lezen.
Basiskennis van recursie.
Probleem 1: Schrijf een programma en een herhalingsrelatie om de Fibonacci-reeks van n te vinden waarbij n>2 .
Wiskundige vergelijking:
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
Herhalingsrelatie:
T(n) = T(n-1) + T(n-2) + O(1)>
Recursief programma:
weergaven en tabellen
Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
Implementatie:
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; }> |
>
>
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) + ' '); }> |
>
>Uitvoer
Fibonacci series of 5 numbers is: 0 1 1 2 3>
Tijdcomplexiteit: O(2N)
Hulpruimte: Op)
Hier is de recursieve boom voor invoer 5, die een duidelijk beeld laat zien van hoe een groot probleem kan worden opgelost in kleinere problemen.
fib(n) is een Fibonacci-functie. De tijdscomplexiteit van het gegeven programma kan afhangen van de functieaanroep.
fib(n) -> niveau CBT (UB) -> 2^n-1 knooppunten -> 2^n functieaanroep -> 2^n*O(1) -> T(n) = O(2^n)
Voor het beste geval.
T(n) = ?(2^n2)>
Werkend:
Probleem 2: Schrijf een programma en een herhalingsrelatie om de faculteit van n te vinden waarbij n>2 .
Wiskundige vergelijking:
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
Herhalingsrelatie:
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
Recursief programma:
Invoer: n = 5
Uitgang:
faculteit van 5 is: 120
Implementatie:
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; }> |
>
Hoe arraylist in Java te sorteren
>
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;> }> |
>
>
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.> > |
>
>Uitvoer
factorial of 5 is: 120>
Tijdcomplexiteit: Op)
Hulpruimte: Op)
Werkend:
Diagram van factoriële recursiefunctie voor gebruikersinvoer 5.
Voorbeeld: echte toepassingen van recursie in echte problemen
Recursie is een krachtige techniek die veel toepassingen kent in de informatica en programmeren. Hier zijn enkele veelvoorkomende toepassingen van recursie:
- Doorkruisen van bomen en grafieken: Recursie wordt vaak gebruikt voor het doorkruisen en doorzoeken van gegevensstructuren zoals bomen en grafieken. Recursieve algoritmen kunnen worden gebruikt om alle knooppunten of hoekpunten van een boom of grafiek op een systematische manier te verkennen. Sorteeralgoritmen: Recursieve algoritmen worden ook gebruikt in sorteeralgoritmen zoals quicksort en merge sort. Deze algoritmen gebruiken recursie om de gegevens in kleinere subarrays of sublijsten te verdelen, ze te sorteren en ze vervolgens weer samen te voegen. Verdeel-en-heers-algoritmen: Veel algoritmen die een verdeel-en-heers-benadering gebruiken, zoals het binaire zoekalgoritme, gebruiken recursie om het probleem op te splitsen in kleinere deelproblemen. Fractale generatie: Fractale vormen en patronen kunnen worden gegenereerd met behulp van recursieve algoritmen. De Mandelbrot-verzameling wordt bijvoorbeeld gegenereerd door herhaaldelijk een recursieve formule toe te passen op complexe getallen. Backtracking-algoritmen: Backtracking-algoritmen worden gebruikt om problemen op te lossen waarbij een reeks beslissingen moet worden genomen, waarbij elke beslissing afhangt van de voorgaande. Deze algoritmen kunnen worden geïmplementeerd met behulp van recursie om alle mogelijke paden te verkennen en terug te gaan wanneer er geen oplossing wordt gevonden. Memoriseren: Memoriseren is een techniek waarbij de resultaten van dure functieaanroepen worden opgeslagen en het in de cache opgeslagen resultaat wordt geretourneerd wanneer dezelfde invoer opnieuw plaatsvindt. Memorisatie kan worden geïmplementeerd met behulp van recursieve functies om de resultaten van subproblemen te berekenen en in het cachegeheugen op te slaan.
Dit zijn slechts enkele voorbeelden van de vele toepassingen van recursie in de informatica en programmeren. Recursie is een veelzijdig en krachtig hulpmiddel dat kan worden gebruikt om veel verschillende soorten problemen op te lossen.
Uitleg: een echt voorbeeld van recursie:
Recursie is een programmeertechniek waarbij een functie zichzelf aanroept. Het kan een krachtig hulpmiddel zijn voor het oplossen van complexe problemen, maar het vereist ook een zorgvuldige implementatie om oneindige lussen en stack-overflows te voorkomen.
Hier is een voorbeeld van het implementeren van recursie in Python:
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
aangepaste uitzondering in 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
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> |
>
>Uitvoer
120>
In dit voorbeeld definiëren we een functie genaamd faculteit, die een geheel getal n als invoer nodig heeft. De functie gebruikt recursie om de faculteit van n te berekenen (d.w.z. het product van alle positieve gehele getallen tot en met n).
De faculteitsfunctie controleert eerst of n 0 of 1 is, wat de basisgevallen zijn. Als n 0 of 1 is, retourneert de functie 1, aangezien 0! en 1! zijn beide 1.
Als n groter is dan 1, komt de functie in het recursieve geval terecht. Het roept zichzelf aan met n-1 als argument en vermenigvuldigt het resultaat met n. Dit berekent n! door recursief te berekenen (n-1)!.
Het is belangrijk op te merken dat recursie inefficiënt kan zijn en tot stackoverflows kan leiden als het niet zorgvuldig wordt gebruikt. Elke functieaanroep voegt een nieuw frame toe aan de aanroepstapel, waardoor de stapel te groot kan worden als de recursie te diep is. Bovendien kan recursie ervoor zorgen dat de code moeilijker te begrijpen en te debuggen is, omdat hierbij moet worden nagedacht over meerdere niveaus van functieaanroepen.
Recursie kan echter ook een krachtig hulpmiddel zijn voor het oplossen van complexe problemen, vooral als het gaat om het opsplitsen van een probleem in kleinere deelproblemen. Bij correct gebruik kan recursie de code eleganter en gemakkelijker leesbaar maken.
Wat zijn de nadelen van recursief programmeren ten opzichte van iteratief programmeren?
Merk op dat zowel recursieve als iteratieve programma's hetzelfde probleemoplossend vermogen hebben, dat wil zeggen dat elk recursief programma iteratief kan worden geschreven en omgekeerd geldt dit ook. Het recursieve programma heeft grotere ruimtevereisten dan het iteratieve programma, omdat alle functies in de stapel blijven totdat het basisscenario is bereikt. Er is ook meer tijd nodig vanwege functieaanroepen en overheadkosten.
Bovendien zijn de codes, vanwege de kleinere codelengte, moeilijk te begrijpen en daarom moet extra voorzichtigheid worden betracht bij het schrijven van de code. De computer heeft mogelijk onvoldoende geheugen als de recursieve oproepen niet goed worden gecontroleerd.
Wat zijn de voordelen van recursief programmeren ten opzichte van iteratief programmeren?
Recursie biedt een schone en eenvoudige manier om code te schrijven. Sommige problemen zijn inherent recursief, zoals boomdoorgangen, Toren van Hanoi , enz. Voor dergelijke problemen verdient het de voorkeur om recursieve code te schrijven. We kunnen dergelijke codes ook iteratief schrijven met behulp van een stapelgegevensstructuur. Zie bijvoorbeeld Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.
Samenvatting van recursie:
- Er zijn twee soorten gevallen in recursie, namelijk een recursief geval en een basisgeval.
- Het basisscenario wordt gebruikt om de recursieve functie te beëindigen wanneer het geval waar blijkt te zijn.
- Elke recursieve aanroep maakt een nieuwe kopie van die methode in het stapelgeheugen.
- Oneindige recursie kan ertoe leiden dat het stapelgeheugen opraakt.
- Voorbeelden van recursieve algoritmen: Merge Sort, Quick Sort, Tower of Hanoi, Fibonacci Series, Factorial Problem, enz.
Op output gebaseerde oefenproblemen voor beginners:
Oefenvragen voor recursie | Set 1
Oefenvragen voor recursie | Stel 2 in
Oefenvragen voor recursie | Set 3
Oefenvragen voor recursie | Set 4
Oefenvragen voor recursie | Stel 5 in
Oefenvragen voor recursie | Set 6
Oefenvragen voor recursie | Stel 7 in
Quiz over recursie
Codeerpraktijk voor recursie:
Alle artikelen over recursie
Recursieve oefenproblemen met oplossingen