czym jest rekurencja?

Rekurencja to proces definiowania czegoś w kategoriach samego siebie.

przykładem świata fizycznego byłoby umieszczenie dwóch równoległych luster naprzeciwko siebie. Każdy obiekt pomiędzy nimi będzie rekurencyjnie odbijany.

funkcja rekurencyjna Pythona

w Pythonie wiemy, że funkcja może wywoływać inne funkcje. Możliwe jest nawet wywołanie samej funkcji. Tego typu konstrukt określa się jako funkcje rekurencyjne.

poniższy obraz przedstawia działanie funkcji rekurencyjnej o nazwierecurse.

Poniżej znajduje się przykład funkcji rekurencyjnej do znalezienia silni liczby całkowitej.

Silnia liczby jest iloczynem wszystkich liczb całkowitych od 1 do tej liczby. Na przykład silnia z 6 (oznaczona jako 6!) jest 1*2*3*4*5*6 = 720.

przykład funkcji rekurencyjnej

def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1))num = 3print("The factorial of", num, "is", factorial(num))

Wyjście

The factorial of 3 is 6

w powyższym przykładziefactorial() jest funkcją rekurencyjną, jak się nazywa.

Kiedy wywołamy tę funkcję z dodatnią liczbą całkowitą, będzie ona rekurencyjnie wywoływać się poprzez zmniejszenie liczby.

każda funkcja mnoży liczbę przez silnię liczby pod nią, aż będzie równa 1. To rekurencyjne wywołanie można wyjaśnić w następujących krokach.

factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

spójrzmy na obraz, który pokazuje krok po kroku proces tego, co się dzieje:

nasza rekurencja kończy się, gdy liczba zmniejsza się do 1. Nazywa się to warunkiem podstawowym.

każda funkcja rekurencyjna musi mieć warunek podstawowy, który zatrzymuje rekurencję, w przeciwnym razie funkcja nazywa się nieskończenie.

interpreter Pythona ogranicza głębokość rekurencji, aby uniknąć nieskończonych rekurencji, co skutkuje przepełnieniem stosu.

domyślnie maksymalna głębokość rekurencji wynosi 1000. Jeśli limit zostanie przekroczony, spowoduje to RecursionError. Spójrzmy na jeden z takich warunków.

def recursor(): recursor()recursor()

Wyjście

Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded

zalety rekurencji

1. funkcje rekurencyjne sprawiają, że kod wygląda czysto i elegancko.
2. złożone zadanie można podzielić na prostsze podproblemy za pomocą rekurencji.
3. generowanie sekwencji jest łatwiejsze przy rekurencji niż przy użyciu jakiejś zagnieżdżonej iteracji.

wady rekurencji

1. czasami logika stojąca za rekurencją jest trudna do naśladowania.
2. wywołania rekurencyjne są drogie (nieefektywne), ponieważ zajmują dużo pamięci i czasu.
3. funkcje rekurencyjne są trudne do debugowania.