Rekurze v Pythonu
Termín rekurze lze definovat jako proces definování něčeho z hlediska sebe sama. Jednoduše řečeno, je to proces, ve kterém funkce volá sama sebe přímo nebo nepřímo.
Výhody použití rekurze
- Složitou funkci lze pomocí rekurze rozdělit na menší dílčí problémy.
- Vytvoření sekvence je jednodušší díky rekurzi než použití jakékoli vnořené iterace.
- Rekurzivní funkce zajišťují, že kód vypadá jednoduše a efektivně.
Nevýhody použití rekurze
- Rekurzivní volání zabírají mnoho paměti a času, což zdražuje použití.
- Rekurzivní funkce jsou náročné na ladění.
- Zdůvodnění rekurze může být někdy těžké promyslet.
Syntax:
def func(): <-- | | (recursive call) | func() ----
Příklad 1: Fibonacciho posloupnost je celočíselná posloupnost 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ýstup
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Příklad 2: Faktoriál 6 je označen jako 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ýstup
Factorial of number 6 = 720
Co je Tail-Recursion?
Jedinečný typ rekurze, kde poslední procedurou funkce je rekurzivní volání. Rekurzi lze zautomatizovat provedením požadavku v aktuálním rámci zásobníku a vrácením výstupu namísto generování nového rámce zásobníku. Koncová rekurze může být optimalizována kompilátorem, díky čemuž je lepší než rekurzivní funkce bez tailu.
Je možné optimalizovat program použitím rekurzivní funkce na konci místo rekurzivní funkce bez konce?
Vezmeme-li v úvahu funkci uvedenou níže, abychom vypočítali faktoriál n, můžeme pozorovat, že funkce nejprve vypadá jako koncová rekurzivní funkce, ale je to nekoncová rekurzivní funkce. Pokud pozorně sledujeme, můžeme vidět, že hodnota vrácená Recur_facto(n-1) je použita v Recur_facto(n), takže volání Recur_facto(n-1) není poslední věcí, kterou Recur_facto(n) provedl.
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ýstup
720
Danou funkci Recur_facto můžeme napsat jako tail-rekurzivní funkci. Cílem je použít ještě jeden argument a ve druhém argumentu přizpůsobíme hodnotu faktoriálu. Když n dosáhne 0, vraťte konečnou 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ýstup
720
