Termen rekursion kan definieras som processen att definiera något i termer av sig själv. Med enkla ord är det en process där en funktion anropar sig själv direkt eller indirekt.
Fördelar med att använda rekursion
- En komplicerad funktion kan delas upp i mindre delproblem med hjälp av rekursion.
- Att skapa sekvenser är enklare genom rekursion än att använda någon kapslad iteration.
- Rekursiva funktioner gör att koden ser enkel och effektiv ut.
Nackdelar med att använda rekursion
- Mycket minne och tid tas genom rekursiva samtal vilket gör det dyrt att använda.
- Rekursiva funktioner är utmanande att felsöka.
- Resonemanget bakom rekursion kan ibland vara svårt att tänka igenom.
Syntax:
konvertera en sträng till datum
def func(): <-- | | (recursive call) | func() ---->
Exempel 1: En Fibonacci-sekvens är heltalssekvensen 0, 1, 1, 2, 3, 5, 8….
Python3
# 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))> |
>
>Produktion
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
Exempel 2: Faktorial av 6 betecknas som 6! = 1*2*3*4*5*6 = 720.
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))> |
katodstrålerörsmonitor
>
understryka med css
>Produktion
Factorial of number 6 = 720>
Vad är svansrekursion?
En unik typ av rekursion där den sista proceduren för en funktion är ett rekursivt anrop. Rekursionen kan automatiseras bort genom att utföra begäran i den aktuella stackramen och returnera utdata istället för att generera en ny stackram. Svansrekursionen kan optimeras av kompilatorn vilket gör den bättre än icke-svansrekursiva funktioner.
Är det möjligt att optimera ett program genom att använda en svansrekursiv funktion istället för icke-svansrekursiv funktion?
Med tanke på funktionen som ges nedan för att beräkna faktorialen för n, kan vi observera att funktionen ser ut som en svansrekursiv till en början men det är en icke-svansrekursiv funktion. Om vi observerar noga kan vi se att värdet som returneras av Recur_facto(n-1) används i Recur_facto(n), så anropet till Recur_facto(n-1) är inte det sista som görs av Recur_facto(n).
Python3
# 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>))> |
>
>Produktion
720>
Vi kan skriva den givna funktionen Recur_facto som en svansrekursiv funktion. Tanken är att använda ytterligare ett argument och i det andra argumentet tar vi hänsyn till värdet av faktorialet. När n når 0, returnera det slutliga värdet för det önskade talets fakultet.
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>))> |
konvertera ett datum till en sträng
>
>Produktion
720>