Rekurzia v Pythone
Pojem rekurzia možno definovať ako proces definovania niečoho z hľadiska seba samého. Jednoducho povedané, je to proces, v ktorom funkcia volá samu seba priamo alebo nepriamo.
Výhody použitia rekurzie
- Zložitú funkciu je možné rozdeliť na menšie čiastkové problémy pomocou rekurzie.
- Vytvorenie sekvencie je jednoduchšie vďaka rekurzii ako použitie akejkoľvek vnorenej iterácie.
- Rekurzívne funkcie spôsobujú, že kód vyzerá jednoducho a efektívne.
Nevýhody použitia rekurzie
- Rekurzívne hovory zaberajú veľa pamäte a času, čo spôsobuje, že používanie je drahé.
- Rekurzívne funkcie sú náročné na ladenie.
- Zdôvodnenie rekurzie môže byť niekedy ťažké premyslieť.
Syntax:
def func(): <-- | | (recursive call) | func() ----
Príklad 1: Fibonacciho postupnosť je celočíselná postupnosť 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))> |
Výkon
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Príklad 2: Faktor 6 je označený ako 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))> |
Výkon
Factorial of number 6 = 720
Čo je Tail-Recursion?
Jedinečný typ rekurzie, kde poslednou procedúrou funkcie je rekurzívne volanie. Rekurzia môže byť automatizovaná vykonaním požiadavky v aktuálnom rámci zásobníka a vrátením výstupu namiesto generovania nového rámca zásobníka. Koncová rekurzia môže byť optimalizovaná kompilátorom, vďaka čomu je lepšia ako non-tail rekurzívne funkcie.
Je možné optimalizovať program použitím chvostovej rekurzívnej funkcie namiesto non-tailovej rekurzívnej funkcie?
Ak vezmeme do úvahy funkciu uvedenú nižšie, aby sme vypočítali faktoriál n, môžeme pozorovať, že funkcia najprv vyzerá ako koncová rekurzívna funkcia, ale je to nerekurzívna funkcia. Ak pozorne sledujeme, môžeme vidieť, že hodnota vrátená Recur_facto(n-1) sa používa v Recur_facto(n), takže volanie Recur_facto(n-1) nie je posledná vec, ktorú vykonal 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> ))> |
Výkon
720
Danú funkciu Recur_facto môžeme napísať ako tail-rekurzívnu funkciu. Cieľom je použiť ešte jeden argument a v druhom argumente prispôsobíme hodnotu faktoriálu. Keď n dosiahne 0, vráťte konečnú hodnotu faktoriálu požadovaného čísla.
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> ))> |
Výkon
720
