Rekursija Python
Rekursijos terminą galima apibrėžti kaip procesą, kai ką nors apibrėžiama savaime. Paprastais žodžiais tariant, tai procesas, kurio metu funkcija save vadina tiesiogiai arba netiesiogiai.
Rekursijos naudojimo privalumai
- Sudėtinga funkcija, naudojant rekursiją, gali būti suskirstyta į smulkesnes problemas.
- Sekos kūrimas yra paprastesnis naudojant rekursiją nei naudojant bet kokią įdėtą iteraciją.
- Dėl rekursinių funkcijų kodas atrodo paprastas ir efektyvus.
Rekursijos naudojimo trūkumai
- Daug atminties ir laiko užima rekursiniai skambučiai, todėl naudojimas yra brangus.
- Rekursyvių funkcijų derinimas yra sudėtingas.
- Rekursijos priežastis kartais gali būti sunku apgalvoti.
Sintaksė:
def func(): <-- | | (recursive call) | func() ----
1 pavyzdys: Fibonačio seka yra sveikųjų skaičių 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))> |
Išvestis
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
2 pavyzdys: 6 faktorialas žymimas kaip 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))> |
Išvestis
Factorial of number 6 = 720
Kas yra uodegos rekursija?
Unikalus rekursijos tipas, kai paskutinė funkcijos procedūra yra rekursinis iškvietimas. Rekursija gali būti automatizuota, įvykdžius užklausą esamame dėklo kadre ir grąžinus išvestį, o ne generuojant naują dėklo kadrą. Kompiliatorius gali optimizuoti uodegos rekursiją, todėl ji yra geresnė už ne uodegos rekursines funkcijas.
Ar galima optimizuoti programą naudojant uodegos rekursinę funkciją, o ne ne uodegos rekursinę funkciją?
Atsižvelgdami į toliau pateiktą funkciją, norėdami apskaičiuoti n faktorialą, galime pastebėti, kad funkcija iš pradžių atrodo kaip uodegos rekursyvinė funkcija, tačiau tai yra ne uodegos rekursyvinė funkcija. Jei atidžiai stebėsime, pamatysime, kad Recur_facto(n-1) grąžinta reikšmė naudojama Recur_facto(n), todėl Recur_facto(n-1) iškvietimas nėra paskutinis Recur_facto(n) dalykas.
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> ))> |
Išvestis
720
Duotą funkciją Recur_facto galime parašyti kaip uodegos rekursinę funkciją. Idėja yra naudoti dar vieną argumentą, o antrajame argumente mes įtraukiame faktorialo reikšmę. Kai n pasiekia 0, grąžinkite galutinę norimo skaičiaus faktorialo reikšmę.
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> ))> |
Išvestis
720
