Terminu Rekursija var definēt kā procesu, kurā kaut kas tiek definēts pats par sevi. Vienkāršiem vārdiem sakot, tas ir process, kurā funkcija izsauc sevi tieši vai netieši.
Rekursijas izmantošanas priekšrocības
- Sarežģītu funkciju var sadalīt mazākās apakšproblēmās, izmantojot rekursiju.
- Sekvences izveide ir vienkāršāka, izmantojot rekursiju, nekā izmantojot jebkuru ligzdotu iterāciju.
- Rekursīvās funkcijas padara kodu vienkāršu un efektīvu.
Rekursijas izmantošanas trūkumi
- Daudz atmiņas un laika aizņem rekursīvie zvani, kas padara to dārgu lietošanu.
- Rekursīvo funkciju atkļūdošana ir sarežģīta.
- Rekursijas pamatojumu dažreiz var būt grūti pārdomāt.
Sintakse:
def func(): <-- | | (recursive call) | func() ---->
1. piemērs: Fibonači secība ir veselu skaitļu secība 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))> |
smtp interneta protokols
>
>Izvade
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
2. piemērs: Faktoriāls 6 tiek apzīmēts kā 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))> |
>
>Izvade
python chr funkcija
Factorial of number 6 = 720>
Kas ir astes rekursija?
Unikāls rekursijas veids, kurā funkcijas pēdējā procedūra ir rekursīvs izsaukums. Rekursiju var automatizēt, izpildot pieprasījumu pašreizējā steka kadrā un atgriežot izvadi, nevis ģenerējot jaunu steka kadru. Kompilators var optimizēt astes rekursiju, kas padara to labāku par ne-astes rekursīvām funkcijām.
Vai ir iespējams optimizēt programmu, izmantojot astes rekursīvo funkciju, nevis astes rekursīvo funkciju?
Ņemot vērā tālāk sniegto funkciju, lai aprēķinātu n faktoriālu, mēs varam novērot, ka funkcija sākotnēji izskatās kā astes rekursīva funkcija, bet tā nav astes rekursīva funkcija. Ja mēs uzmanīgi novērojam, mēs varam redzēt, ka Recur_facto(n-1) atgrieztā vērtība tiek izmantota Recur_facto(n), tāpēc Recur_facto(n-1) izsaukums nav pēdējais, ko veic 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>))> |
>
>Izvade
720>
Doto funkciju Recur_facto varam uzrakstīt kā astes rekursīvu funkciju. Ideja ir izmantot vēl vienu argumentu, un otrajā argumentā mēs iekļaujam faktoriāla vērtību. Kad n sasniedz 0, atgriež vajadzīgā skaitļa faktoriāla galīgo vērtību.
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>))> |
>
>Izvade
720>