Rekurencja w Pythonie

---

powrót

Rekurencja jest techniką wykorzystująca wywoływanie funkcji przez samą siebie. W trakcie jej wywołania tworzona jest kopia tej funkcji, a każda kopia to równoważna jest z przydzieleniem nowych zasobów pamięciowych. Skoro tak, należy pamiętać, że zbyt duża liczba wywołań funkcji może spowodować problemy z pamięcią. Rozwiązując problem rekurencyjnie, należy zadbać oto, aby nasza funkcja nie zagnieżdżała się w nieskończoność. Musi istnieć warunek, który spowoduje, że rekurencja od pewnego momentu przestanie się wykonywać.

Rozwiązywanie problemów tą techniką w wielu przypadkach jest prostsze niż techniką iteracyjną (pętlą).

Przykład 1

Rozwiążmy problem, który wyznaczy silnię z liczby naturalnej n. Przypomnijmy, że silnia z liczby n jest to iloczyn kolejnych liczb naturalnych począwszy od 1 zakończywszy na n, np. $$3! = 3\cdot2\cdot1=6$$Znak wykszyknika czytaj jako silnia np. 3! — trzy silnia, oraz 0! = 1.

def silnia(n):
    if n > 1: # jeśli n jest większe od 1, to wyznacz n * silnia(n-1)
        return n*silnia(n-1) # funkcja wywołuje samą siebie (tworzy swoją kopię)
    return 1 # w przeciwnym wypadku zwróć 1 (instrukcja else jest tu zbędna)

# --------blok główny programu -----------
print(silnia(4)) # 24

W przypadku gdy n = 0 lub n = 1 funkcja zwróci 1, czyli w tym miejscu kończy się rekurencyjne wywołanie funkcji silnia. Dla argumentu równego 4 program działa następująco:

$$silnia(4) = 4\cdot silnia(3) = 4\cdot 3 \cdot silnia(2)=4\cdot 3\cdot 2 \cdot silnia(1) = 4\cdot 3\cdot 2\cdot 1$$

Zauważamy, że w miejsce silnia(n) wstawiamy $$n\cdot silnia(n-1)$$ lub 1, jeśli wywołana zostanie funkcja z argumentem mniejszym od 2.

Przykład 2

Napisz program, który wypisze litery z wczytanego wyrazu w odwrotnej kolejności.

Rozwiązanie

def odwroc(napis, nr):
   print(napis[nr], end='') # wypisz literę na pozycji nr
   if nr > 0: # jeśli nie wypisaliśmy wszystkich liter
       odwroc(napis, nr - 1) # to wywołaj rekurencyjnie funkcję odwroc wskazującą na literę stojącą tuż przed wyświetlaną

# --------blok główny programu -----------
napis = input() 
odwroc(napis, len(napis) - 1) # drugim argumentem jest indeks, pod którym znajduje się ostatnia do wyświetlenia litera

Zauważ, że nie występuje tu słowo return, ponieważ wynik nie zostaje zwracany tylko wypisywany na ekran (na wyjście).

Przykład 3 — przykład 2 inaczej

def odwroc(napis, nr):
    if nr < len(napis):
        odwroc(napis, nr + 1) # wchodzimy w rekurencję tak długo jak się da
        print(napis[nr], end='') # a przy jej nawrocie zbieramy wyniki

# --------blok główny programu -----------
napis = input() # lokomotywa
odwroc(napis, 0) # awytomokol

Wyobraź sobie, że schodzisz po schodach. Pierwszy schodek to pierwsza litera, zostawiasz ją na schodku, ale jej nie wypisujesz i dajesz krok (wywołujesz rekurencję) i jesteś na drugim schodku, tu zostawiasz drugą literę, i kolejny krok (trzecia litera) itd. Dając kroki nie wypisywałeś tych liter, ponieważ w pierwszej kolejności uruchamiałeś rekurencyjnie kolejną wersję funkcji odwroc, dlatego, że instrukcja print występuje pod wywołaniem funkcji odwroc. Gdy dotarliśmy do ostatniej litery (warunek if nr < len(napis): nie jest spełniony) czas na wypisywanie wyników (print(napis[nr], end='')), robimy więc nawrót i wracamy tą samą drogą wypisując kolejne litery począwszy od ostatniej i zakończywszy na pierwszej.