Rekurencja

Co może pójść źle?¶

Może się nie skończyć. Dokładniej to zawsze się skończy - może się skończyć RecursionError. Chodzi o to, że Python liczy ile poziomów rekurencji zrobiliśmy i jak jest tego za dużo to przerywa program.

Dlaczego przerywa? Jak napisałem w opisie przestrzeni nazw każde wywołanie funkcji wymaga osobnej przestrzeni nazw. To jest miejsce w pamięci, które można wykorzystać lepiej. Chociaż istotniejsze jest to, że mijesce na przestrzenie nazw jest mniejsze niż te gigabajty, które mają nasze komputery. No więc przestrzeń, na której odkładane są kolejne przestrzenie przestrzenie nazw i różne inne rzeczy. Ta przestrzeń to stos, po angielsku stack. Po angielsku przepełnienie to overflow, a exception to wyjątek. Tak więc opisana sytuacja to StackOverflow Exception. I już wiadomo skąd się wzięła nazwa jednej strony.

Wyjątek, z punktu widzenia naszego kodu, jest to sytuacja wyjątkowa, a -normalna i trzeba to zasygnalizować - natychmiast. Chodzi o to, że jeżeli wiadomo, że coś idzie źle to trzeba przerwać działanie, żeby nie napsuć i, żeby było dokładniej wiadomo co poszło źle. Do sygnalizowania błędów służą wyjątki - ang. exceptions. Czasem to my robimy, czasem biblioteka, której używamy. Ważne, że się dowiadujemy szybko - ang. fail fast.

Dość teorii - trzeba zakodzić.

Sumowanie rekurencyjne¶

Załóżmy, że chcemy zsumować liczby do n. Suma liczb do n to suma do n-1 plus nasze n:

def sum(n):
    if type(n) != int or n < 0:
        raise Exception("Expected integer, greater then zero.")
    if n == 0:
        return 0
    else:
        return sum(n - 1) + n

Pierwszy if - jak typ przekazanego parametru nie jest int lub liczba jest mniejsza od zera to... Tutaj widać dlaczego wyrażenia logiczne nie muszą być przetwarzane do końca. W pierwszym kroku sprawdzamy, czy to jest liczba całkowita, a potem, o ile jest to liczba całkowita, sprawdzamy, czy jest mniejsza od zera. Jak pierwsza część nie jest prawdą, to wykonywanie drugiej zwróci błąd, bo np. przekazaliśmy ciąg znaków..

Ogólnie to - sprawdzamy poprawność przekazanych danych - jak przekazany parametr to np. ciąg znaków - nie ma sensu wykonywać dalszej pracy. Jak już na początku pisałem - "rzucamy" wyjątkiem. W Javie zamiast raise, jest throw, czyli tłumacząc na Polski - nie podnosimy wyjątku tylko rzucamy. Chodzi dokładnie o to samo - program się przerwie. Na ekranie wypisze gdzie jest błąd i nasz opis.

Po co tak? A to zakomemtujcie tego if`a i wywołajcie funkcję z parametrem ``1.5`. Co się stanie? A no funkcja się będzie wywoływać, ale warunek z drugiego if`a nigdy nie będzie spełniony i dostaniemy `RecursionError, razem z zestawem informacji, które ewentualnie mają nam pomóc zorientować się w sytuacji.

Wróćmy do rekurencji. A co jak chciałbym, żeby program wypisał całe działanie?

def sum_str(n):
    if type(n) != int or n < 0:
        raise Exception("Expected integer, greater then zero.")
    if n == 0:
        return '0'
    else:
        return sum(n - 1) + ' + ' + str(n)

Działa, ładnie wypisuje. Trzeba tylko pamiętać, że dodawanie liczb i ciągów znaków nie działa - trzeba wykonać konwersję. ' + ' to ciąg znaków, który znajdzie się między wynikiem wywołania sum, a konwesją.

Chociaż, pewnie celem nie było pokazanie tej operacji.

Oczywiście, że tak. Tak prostą rekurencję da się zapisać o wiele prościej:

def sum(n):
    if type(n) != int or n < 0:
        raise Exception("Expected integer, greater then zero.")
    res = 0
    for i in range(n):
        res += i + 1
    return res

def sum_str(n):
    if type(n) != int or n < 0:
        raise Exception("Expected integer, greater then zero.")
    res = '0'
    for i in range(n):
        res += ' + ' + str(i + 1)
    return res

Funcja range daje nam możliwość przejścia pętlą po liście liczb zaczyna od zera, kończy na n-1. Dlatego jest i+1. Operacja += to dodanie - bierze zmienną, w tym wypadku res i dodaje do niej to co jest po prawej stronie, i całość zapisuje spowrotem do zmiennej - res. Inaczej trzeba by napisać np.:

res = res + ' + ' + str(i + 1)

Wniosek jest taki, że czasem łatwiej opisać coś rekurencją, a czasem pętlą. To twój wybór.

Ciąg Fibonacciego¶

To jest standardowy przykład używany przy omawianiu rekurencji. Definicja ciągu Fibonacciego - pierwsze dwa wyrazy to jeden, a każdy, kolejny to suma dwóch poprzednich.

Implementacja wygląda tak:

def fib(n):
    if type(n) != int or n < 0:
        raise Exception("Expected integer, greater then zero.")
    if n <= 1:
        return 1

    return fib(n - 1) + fib(n - 2)

Wyrazy numerowane są od zera, czyli dla parametru n równego zero, albo jeden zwrócona jest wartość jeden. Potem wywołujemy rekurencyjnie.

Czy to jest dobry kod? Działa, jest czytelny, ale... Policzmy w pamięci pierwsze parę kroków - powiedzmy od 5. Wywołujemy dla 4 i dla 3. Potem z czwórki wywołujemy dla 3 i 2 - i już widać, że trójkę liczymy dwa razy. Chyba pętla lepiej się sprawdzi.

def fib(n):
    if type(n) != int or n < 0:
        raise Exception("Expected integer, greater then zero.")
    if n <= 1:
        return 1
    res = 1
    n_1 = 1
    n_2 = 1
    for i in range(1, n):
        res = n_1 + n_2
        n_2 = n_1
        n_1 = res
        # print(f"{i}: {n_2} {n_1} -> {res}")
    return res

Dla zera i jeden zwaracamy jeden, bez "zastanawiania się". Patrząc na kod z poprzedniego przykładu - trzeba pamiętać dwa poprzenie kroki. Wyliczamy wynik, dla danego kroku - res, a następnie zapamiętujemy dwa poprzednie kroki. Czyli wartość "minus jeden" teraz będzie minus dwa. A wynik wpisujemy do kroku poprzedniego, bo tak sytuacja będzie wyglądała dla następnego przebiegu.

Jakiś przykład z życia?¶

Załóżmy, że trzeba wykonać jakąś operację na wszystkich plikach w katalogu, ale też jego podkatalogach, podkatalogach podkatalogów i tak dalej, i tak dalej.

Potrzebujemy funkcji, która wykona zadaną pracę dla listy lików i wykona samą siebie dla każdego podkatalogu. Założenie jest takie, że katalogi mają skończoną ilość poziomów. Z uwagi na ograniczone miejsce na dysku - to sensowne założenie. Kod, który wypisuje nazwę pliku, uwzględniając pełną ścieżkę i wielkość pliku:

import os

def proc_dir(location):
    print(f"visiting - {location}")
    entries = os.listdir(location)
    for e in entries:
        e_dir = os.path.join(location, e)
        if os.path.isdir(e_dir):
            proc_dir(e_dir)
        if os.path.isfile(e_dir):
            size = os.path.getsize(e_dir)
            print(f'found file - {e_dir} - {size}')

proc_dir('/home/mzaborow/workspace/priv')

Używamy modułu os, zawierającego sporo rzeczy potrzebnych do operowania na zasobach systemu operacyjnego. Moduł zawiera podmoduły - jak path, już używanego tutaj mudłu. Tym razem sprawdzamy, czy wpis w katalogu jest podkatalogiem, plikiem, sprawdzamy wielkość pliku - to wszystko co jest potrzebne.

Czy da się zamienić to na pętlę? Pewnie, że się da. Wyobraźcie sobie, że mamy listę katalogów do przejrzenia, pobieramy pierwszy element z tej listy i go przeglądamy - podkatalogi wkładamy na tę listę, a z plikami robimy to, co trzeba. Co więcej chodzenie po drzewie to dość częsta operacja i jest do tego gotowa funkcja - walk:

import os

for dir, dir_names, file_names in os.walk('/home/mzaborow/workspace/priv'):
   for name in file_names:
      e_dir = os.path.join(dir, name)
      size = os.path.getsize(e_dir)
      print(f'found file - {e_dir} - {size}')

Podsumowanie¶

Rekurencja to trudny temat. Kiedyś, to była granica między koderem a kimś, kto zajmuje się programowaniem hobbystycznie. Dziś, dzięki takim rozwiązaniom jak walk nie jest takie istotne. Chociaż może jest, ale mnie już o to je pytają.