Rekurencja w Pythonie
Termin rekursję można zdefiniować jako proces definiowania czegoś w kategoriach samo w sobie. Krótko mówiąc, jest to proces, w którym funkcja wywołuje się bezpośrednio lub pośrednio.
Zalety stosowania rekurencji
- Skomplikowaną funkcję można podzielić na mniejsze podproblemy, korzystając z rekurencji.
- Tworzenie sekwencji jest prostsze dzięki rekurencji niż wykorzystanie jakiejkolwiek zagnieżdżonej iteracji.
- Funkcje rekurencyjne sprawiają, że kod wygląda na prosty i skuteczny.
Wady stosowania rekurencji
- Wywołania rekurencyjne zajmują dużo pamięci i czasu, co czyni je kosztownymi w użyciu.
- Funkcje rekurencyjne są trudne do debugowania.
- Czasami trudno jest przemyśleć uzasadnienie rekurencji.
Składnia:
def func(): <-- | | (recursive call) | func() ----
Przykład 1: Ciąg Fibonacciego to ciąg liczb całkowitych 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))> |
Wyjście
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Przykład 2: Silnia liczby 6 jest oznaczana 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))> |
Wyjście
Factorial of number 6 = 720
Co to jest rekurencja ogonowa?
Unikalny typ rekurencji, w którym ostatnią procedurą funkcji jest wywołanie rekurencyjne. Rekursję można zautomatyzować, wykonując żądanie w bieżącej ramce stosu i zwracając dane wyjściowe zamiast generować nową ramkę stosu. Rekursja ogona może zostać zoptymalizowana przez kompilator, co czyni ją lepszą niż funkcje rekurencyjne bez ogona.
Czy można zoptymalizować program, korzystając z funkcji rekursywnej z ogonem zamiast funkcji rekurencyjnej bez ogona?
Biorąc pod uwagę funkcję podaną poniżej w celu obliczenia silni n, możemy zauważyć, że funkcja ta na początku wygląda jak funkcja rekurencyjna z ogonem, ale nie jest to funkcja rekursywna z ogonem. Jeśli przyjrzymy się uważnie, zobaczymy, że wartość zwrócona przez Recur_facto(n-1) jest używana w Recur_facto(n), więc wywołanie Recur_facto(n-1) nie jest ostatnią rzeczą wykonaną przez 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> ))> |
Wyjście
720
Możemy zapisać podaną funkcję Recur_facto jako funkcję rekursywną. Pomysł jest taki, aby użyć jeszcze jednego argumentu, a w drugim argumencie uwzględnimy wartość silni. Gdy n osiągnie 0, zwróć końcową wartość silni żądanej liczby.
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> ))> |
Wyjście
720
