De term recursie kan worden gedefinieerd als het proces waarbij iets in termen van zichzelf wordt gedefinieerd. In eenvoudige bewoordingen is het een proces waarbij een functie zichzelf direct of indirect aanroept.
Voordelen van het gebruik van recursie
- Een ingewikkelde functie kan met behulp van recursie worden opgesplitst in kleinere deelproblemen.
- Het maken van reeksen is eenvoudiger door middel van recursie dan door het gebruik van geneste iteratie.
- Recursieve functies zorgen ervoor dat de code er eenvoudig en effectief uitziet.
Nadelen van het gebruik van recursie
- Er wordt veel geheugen en tijd in beslag genomen door recursieve oproepen, wat het gebruik ervan duur maakt.
- Recursieve functies zijn een uitdaging om te debuggen.
- De redenering achter recursie kan soms moeilijk te doorgronden zijn.
Syntaxis:
def func(): <-- | | (recursive call) | func() ---->
Voorbeeld 1: Een Fibonacci-reeks is de gehele reeks van 0, 1, 1, 2, 3, 5, 8….
Python3
alfabet naar cijfers
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> >if> n <>=> 1>:> >return> n> >else>:> >return>(recursive_fibonacci(n>->1>)>+> recursive_fibonacci(n>->2>))> n_terms>=> 10> # check if the number of terms is valid> if> n_terms <>=> 0>:> >print>(>'Invalid input ! Please input a positive value'>)> else>:> >print>(>'Fibonacci series:'>)> for> i>in> range>(n_terms):> >print>(recursive_fibonacci(i))> |
>
>Uitvoer
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
Voorbeeld 2: De faculteit van 6 wordt aangeduid als 6! = 1*2*3*4*5*6 = 720.
java regex $
Python3
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> >if> n>=>=> 1>:> >return> n> >else>:> >return> n>*> recursive_factorial(n>->1>)> # user input> num>=> 6> # check if the input is valid or not> if> num <>0>:> >print>(>'Invalid input ! Please enter a positive number.'>)> elif> num>=>=> 0>:> >print>(>'Factorial of number 0 is 1'>)> else>:> >print>(>'Factorial of number'>, num,>'='>, recursive_factorial(num))> |
>
>Uitvoer
Factorial of number 6 = 720>
Wat is staartrecursie?
Een uniek type recursie waarbij de laatste procedure van een functie een recursieve aanroep is. De recursie kan worden geautomatiseerd door het verzoek uit te voeren in het huidige stapelframe en de uitvoer terug te sturen in plaats van een nieuw stapelframe te genereren. De staartrecursie kan door de compiler worden geoptimaliseerd, waardoor deze beter is dan niet-staartrecursieve functies.
Is het mogelijk om een programma te optimaliseren door gebruik te maken van een staart-recursieve functie in plaats van een niet-staart-recursieve functie?
Als we de onderstaande functie beschouwen om de faculteit van n te berekenen, kunnen we waarnemen dat de functie er in eerste instantie uitziet als een staart-recursief, maar dat het een niet-staart-recursieve functie is. Als we goed kijken, kunnen we zien dat de waarde die wordt geretourneerd door Recur_facto(n-1) wordt gebruikt in Recur_facto(n), dus de aanroep van Recur_facto(n-1) is niet het laatste dat door Recur_facto(n) wordt gedaan.
Python3
c programmareeksarray
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > >if> (n>=>=> 0>):> >return> 1> > >return> n>*> Recur_facto(n>->1>)> > # print the result> print>(Recur_facto(>6>))> |
>
>Uitvoer
720>
We kunnen de gegeven functie Recur_facto schrijven als een staart-recursieve functie. Het idee is om nog een argument te gebruiken en in het tweede argument passen we de waarde van de faculteit toe. Wanneer n 0 bereikt, retourneert u de uiteindelijke waarde van de faculteit van het gewenste getal.
zure eigenschappen
Python3
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a>=> 1>):> > >if> (n>=>=> 0>):> >return> a> > >return> Recur_facto(n>-> 1>, n>*> a)> > # print the result> print>(Recur_facto(>6>))> |
>
>Uitvoer
720>