Funkcje rekurencyjne w Python, podobnie jak programowanie obiektowe, nie są pojęciem, bez którego nie możemy skutecznie programować. Jednak są kolejnym narzędziem w naszym arsenale, które poszerzają nasze umiejętności i sprawią, że rozwiązanie niektórych problemów, stanie się prostsze. Poniżej nauczymy się, czym są funkcje rekurencyjne i jak je wykorzystać w praktyce. Zaczynajmy!

W najprostszym tłumaczeniu, możemy powiedzieć, że są to funkcje, które aby rozwiązać dany problem, wywołują same siebie.

Przykład 1, funkcji rekurencyjnej, w Python

Jako nasz pierwszy przykład, postawmy sobie przeszukanie listy liczb [1,3,7,11,17,23], pod kątek występowania liczby 17.

Rozwiązanie z użyciem pętli for, mogło by wyglądać następująco:

lista = [1,3,7,11,13,17,23]
cel = 17

count = 0
for i in lista:
    if i == cel:
        print("Znalazłem, na pozycji", count)
        break
    else: 
        if count == len(lista)-1:
            print("Nie znalazłam celu")
    count+=1

Rozwiązanie tego problemy, z użyciem funkcji rekurencyjnej, w języku Python:

lista = [1,3,7,11,13,17,23]
cel = 17

def szukaj(lista, cel, pozycja):
    
    if lista[pozycja] == cel:
        print("Znalazłem na pozycji", pozycja)
        return
    elif pozycja == len(lista)-1:
        print("Nie znalazłam celu")
        return
    szukaj(lista, cel, pozycja+1)
        
szukaj(lista, cel, 0)

Co się dzieje?

  1. Tworzymy funkcję ‚szukaj’, która przyjmuje jako parametr, listę, nasz cel, oraz pozycję, która jest sprawdzana pod kątem celu
  2. Wywołujemy nasza funkcję, a jako pozycja, podajemy liczbę 0, będącą odpowiednikiem pierwszej pozycji w liście, do sprawdzenia
  3. Funkcja, sprawdza czy element w liście, znajdujący się na tej pozycji, jest tym, którego szukamy. Jeżeli tak, to drukujemy komunikat, że go znaleźliśmy
  4. Jeżeli nie, to sprawdzamy czy to był ostatni element na liście, jeżeli tak, to drukujemy komunikat, że liczby którą szukamy nie ma na liście
  5. Jeżeli nie, to funkcja, wywołuje sama, siebie, lecz z ‚pozycja+1’, czyli wywołana funkcja, sprawdzi kolejny element na liście.
  6. I tak dalej.

Obydwa rozwiązania, zwrócą, dokładnie ten sam efekt, a mianowicie „Znalazłem na pozycji 5”. Prawdą również jest, że każdą funkcję rekurencyjną, da się zamienić na pętle ‚for’. Tak samo jak każdą pętle ‚for’, możemy zapisać w postaci funkcji rekurencyjne.

W takim razie, po co nam są funkcje rekurencyjne, w Python?

Jak się okazuje, rozwiązania niektórych problemów, są bardziej eleganckie, przy użyciu funkcji rekurencyjnych.

Zwolennicy Big Data, i systemów rozproszonych, powiedzą, że programy oparte o funkcje rekurencyjne, są łatwiejsze do przetwarzania.

Zwolennicy funkcji rekurencyjnych, argumentują ich użycie, miedzy innymi czytelniejszym kodem źródłowym oraz bardziej przejrzystą logiką programu.

I faktycznie, początkowo, wydają się skomplikowanym, zbytkiem, jednak w momencie kiedy nabierzemy, wprawy, okaże się, że sami zaczniemy w naturalny sposób z nich korzystać. Jestem pewien, że osoby programujące w językach Scala czy Haskell, to potwierdzą, gdyż funkcje rekurencyjne stanowią, jedną z podstaw programowania, w tych językach. Tak samo jak innych językach programowania funkcyjnego, o których zresztą będziemy nie raz rozmawiać na analityk.edu.pl.

Przykład 2, funkcji rekurencyjnej, w Python:

Przyjrzyjmy się innemu przykładowi funkcji rekurencyjnej. Mianowicie napiszmy funkcję, która pobiera jako parametr łańcuch znaków i zamienia małe litery na wielki, i na odwrót, po czym zwraca zamieniony łańcuch znaków.

tekst = "Dawno, dawno, temu. Na odległej stronie, o analizie danych i AI..."

def zamień(tekst, pozycja):
    
    if tekst[pozycja].isupper():
        tekst = tekst[0:pozycja] + tekst[pozycja].lower() + tekst[pozycja+1:]
    else:
        tekst = tekst[0:pozycja] + tekst[pozycja].upper() + tekst[pozycja+1:]
    
    if pozycja == len(tekst)-1: return tekst;
    
    return zamień(tekst, pozycja+1)
    
print(zamień(tekst, 0))

Co się dzieje?

  1. Wiele rzeczy jest podobnych do przykładu 1. Funkcja pobiera łańcuch, oraz pozycję w łańcuchu, od której ma zacząć sprawdzanie.
  2. Za pomocą funkcji ‚isupper()’, sprawdzamy czy litera w łańcuchu na tej pozycji jest wielka. Jak jest to tworzymy łańcuch na nowo. Łańcuchy nie wspierają podmiany pojedynczej litery, tak jak lista wspiera podmianę jednego elementu, dlatego musimy łańcuch utworzyć na nowo: najpierw część do tej pozycji, potem zamieniamy literę na pozycji na małą, a na końcu dodajemy resztę łańcucha.
  3. Analogicznie robimy, jeżeli litera jest mała
  4. później sprawdzamy czy parametr ‚pozycja’, wskazuje na koniec łańcucha, jeżeli tak, to zwracamy łańcuch, za pomocą ‚ return tekst ‚
  5. A jeżeli to nie koniec, to ponownie wywołujemy funkcję, przesuwając pozycję o 1 do przodu.

Przykład3, funkcji rekurencyjnej, Python – wyszukiwanie binarne, przy użyciu funkcji rekurencyjnej:

Osoby, które wykonały kurs Ćwiczenia i zadania Python, dla początkujących, mogą pamiętać, zadanie Wyszukiwanie binarne, które polega na przeszukiwaniu posortowanej listy liczb, pod kątem występowania, szukanej liczby. Na tamtą, chwilę, w celu rozwiązania tego zadania użyliśmy pętli ‚while’, natomiast samo rozwiązanie wyglądało następująco:

    def search (array, target): 
        
        left = 0 
        right = len(array) 
        index = 0 
        
        while left < right: 
            
            index = (left + right) // 2 
            
            if array[index]==target_number: 
                return index 
            else: 
                if array[index]<target_number: 
                    left = index+1 
                else: 
                    right = index 
                    
        return -1 
            
    A = [1,3,4,5,7,9,11,15,16,17,19] 
    target_number = 8 
    index = search(A, target_number)
    print (index)

To samo zadanie, rozwiązane przy użyciu funkcji rekurencyjnej, w Pyton, wygląda następująco:

def wSzybkie(lista, początek, koniec, cel):
    
    if początek > koniec: return False
    x = (początek+koniec)//2

    if lista[x] == cel: print("mam"); return x
    if lista[x] < cel: return wSzybkie(lista, x+1, koniec, cel)
    if lista[x] > cel: return wSzybkie(lista, początek, x-1, cel) 

lista = [1,3,7,44,55,66,78,89,123,134]
cel = 90

print ( wSzybkie(lista, 0, len(lista)-1, cel) )

Można pokusić się o stwierdzenie, że jest ono czytelniejsze. Funkcja, dzieli zbiór na 2. Sprawdza, czy znalazła szukaną liczbę, a jeżeli nie, to wywołuje sama siebie, ale już nie dla całej listy, a dla połówki, którą teraz będzie przeszukiwać.

Podsumowanie. Rekurencje są nową koncepcją, którą może być ciężko przyswoić ‚z biegu’. Jednak życie pokazuje, że jest to koncepcja po którą coraz częściej sięgają analitycy danych oraz programiści. W pierwszej kolejności proponujemy powtórzenie w/w przykładów, we własnym środowisku programistycznym, jak Jupyter Notebook. W drugiej kolejności rozwiązanie ćwiczeń, znajdujących się na końcu naszej lekcji.

W następnej lekcji, zajmiemy się tematyką, wykorzystywania Python do pisana skryptów, tak aby pewnym krokiem, zmierzać, do kolejnego mini projektu, w którym tym razem, wystąpimy w roli tajnego agenta, który musi włamać się do systemu. Na szczęście jest on zaznajomiony z programowaniem funkcyjnym w Python, co mu znacząco ułatwi zadanie 🙂

Ćwiczenie

Ćwiczenie 1: Napisać funkcję rekurencyjna, przyjmującą jako parametr listę, a zwracającą, ilość liczb jaką przechowuje. Lista, może zawierać również ciągi znaków, i wyglądać przykładowo tak:

lista = [1,3,7,’abc,11]

Funkcja, powinna zwrócić liczbę 4

Rozwiązanie 1:

lista = [1,3,7,'abc',11,'zxy']

def zlicz(lista, pozycja, ilość):
    if pozycja == len(lista): return ilość
    if type(lista[pozycja]) == int: return zlicz(lista, pozycja+1, ilość+1)
    else: return zlicz(lista, pozycja+1, ilość)
        
zlicz(lista,0,0)

Python, NIE tylko dla początkujących

  1. Wstęp do kursu
  2. Moduły i pakiety
  3. Programowanie obiektowe – wstęp
  4. Programowanie obiektowe – dziedziczenie
  5. Programowanie obiektowe – hermetyzacja
  6. Mini projekt – Organizer
  7. Funkcje rekurencyjne w Python <– bieżąca lekcja
  8. Pisanie skryptów w Python
  9. Mini projekt – tajny agent, generator haseł
  10. *args oraz **kwargs
  11. Dekoratory w Python
  12. Mini projekt – tajny agent – kontakty
  13. Odwzorowanie list
  14. Podsumowanie oraz dalsze kroki