Szybki Python 101 – vol. 7

Poznaliśmy wiele ciekawych elementów Pythona. To dobry moment, aby na chwilę się od tego oderwać i bardziej skoncentrować na pewnych podstawach myślenia algorytmicznego i poznać podstawowe narzędzia do rozwiązywania różnych problemów.

Skupimy się tutaj na dwóch pojęciach, iteracji i rekurencji, postaramy się za ich pomocą rozwiązać kilka problemów algorytmicznych.

Iteracja – powtórz n razy

Iteracja czyli używanie pętli. Napiszmy sobie funkcję, która wypisze nam jakiś tekst n razy, korzystając z pętli. Nie jest to raczej jakieś wielkie wyzwanie, poznaliśmy wszystkie elementy Pythona, które nam to umożliwią.

Dla przypomnienia: powtórzyć coś n razy:

for _ in range(3):
    print("Hello World!")

# Hello World!
# Hello World!
# Hello World!

Napisać funkcję, która wypisze jakiś tekst:

def say_hello():
    print("hello world")

say_hello()
#hello world

Napisać funkcję, która przyjmuje jakiś argument i coś z nim robi:

def times_two(n):
    return n * 2

print(times_two(10)) #20

Połączyć to wszystko w jedną całość i mamy nasz program, który wypisuje „hello world” n razy:

def n_hello(n):
    for _ in range(n):
        print("Hello World")

n_hello(4)
# Hello World
# Hello World
# Hello World
# Hello World

Jest to rozwiązanie iteracyjne, czyli wykorzystujące pętlę.

Rekurencja – powtórz n razy

Ten sam problem możemy rozwiązać za pomocą rekurencji. Jest to podejście, w którym funkcja posiada pewien warunek, który kończy jej wykonanie, jak również wywołanie samej siebie. I będzie samą siebie wywoływać, aż warunek kończący zostanie spełniony.

Jak działa nasza funkcja powtórz n razy w wersji rekurencyjnej?

def hello_rec(n):
    if n == 0:
        return
    print("Hello World")
    hello_rec(n-1)

hello_rec(3)

# Hello World
# Hello World
# Hello World

Mamy funkcję hello rec. Przyjmuje ona tak samo warunek n. Jeżeli n jest równe zero mamy słówko kluczowe return, które oznacza wyjście z funkcji i zwrócenie wartości (funkcje „printujące” niczego nie zwracają, ale w rekurencji wyjście z funkcji musi zostać zaznaczone, stąd słówko return bez niczego).

Ale nasze n to nie jest 0, tylko 3. W takim wypadku Wypisujemy hello world i wywołujemy funkcję hello_rec wewnątrz niej samej, ale z n zmienionym na n-1.

Nasze n równa się 2. Po raz kolejny piszemy hello world i wywołujemy hello_rec z niej samej, n-1 czyli 1.

Raz jeszcze piszemy hello world, wywołujemy hello_rec z niej samej, tym razem n-1 czyli 0. I spełnia nasz warunek wyjścia a jako że mamy funkcję „printującą” czyli nie zwracającą niczego, mamy tam pusty return.

Trochę trzeba nad tym posiedzieć aby zrozumieć pokrętną, rekurencyjną logikę, ale warto.

Silnia – iteracja

Silnia to takie coś, co dla 2 daje 1 * 2. Dla 3 1*2*3. I tak dalej, silnia dla 4 to 1*2*3*4. Można ten problem rozwiązać iteracyjnie, czyli w pętli.

Tutaj mamy przykład z internetu jak się za to zabrać:

def factorial(n):
    fact = 1
    for num in range(2, n + 1):
        fact *= num
    return fact

print(factorial(2)) #2
print(factorial(3)) #6

Czyli tak, silnia 2 ma dać 1 * 2. A zatem zmienna fact równa 1, bo w każdej silnii zaczynamy od 1. Następnie w zakresie od 2 do 2+1 czyli w zakresie od 2 do 3 ale bez 3, mnożymy fact przez num, tutaj 2.

Możemy to sobie przeanalizować na kartce papieru, ale jest to taki algorytm i działa.

Załóżmy, że mamy silnię 3, czyli mamy dostać 1 * 2 * 3.

1 już mamy, zmienna fact. W zakresie od 2 do 3+1 czyli w zakresie od 2 do 4 bez 4, mnożymy fact (1) najpierw przez 2, potem przez 3 (4 już nie).

Zwracamy wynik mnożenia 1 * 2 * 3 dla argumentu 3. Działa. Chodzi. Wszystko w pętli, czyli iteracyjnie.

Nie są to najłatwiejsze zadania, ale zawsze można je na chłodno przeanalizować i zrozumieć, jak co działa.

Silnia – rekurencyjnie

Funkcja rekurencyjna wywołuje samą siebie aż spełniony zostanie „warunek wyjścia”. Ponadto silnia to już funkcja, która coś zwraca, a zatem będzie ciekawie.

Oto nasz przykład rekurencyjnego rozwiązania silnii:

def fact_rec(n):
    if n == 1:
        return n
    return n * fact_rec(n-1)


print(fact_rec(2)) #2
print(fact_rec(3)) #6

Działamy w ten sposób – jeżeli n jest równe 1, zwróć n (czyli 1). Jeżeli jest większe, zwróć wynik mnożenia n razy silnia n – 1.

Czyli po ludzku – bierzesz dwa? Okej, 2 to nie jeden. Zwróć mi wynik z mnożenia 2 razy wywołanie mnie samej ale z 2-1.

A zatem wywołuję się z wnętrza funkcji, ale z n jako 2-1 czyli z 1. Warunek spełniony, zwracam n. Czyli 1. Okej, ale jeszcze coś mi tam leży do zrobienia.

To coś, to było 2 razy wynik tego, co już mam, czyli 1. Aha, zwróć 2 * 1. Gotowe.

Dla silnii równej 3 ten proces po prostu powtarzamy jeden raz więcej. Zaczynamy od 3, mnożymy 3 * silnia 2. Silnia 2 to 2 * silnia 1. Silnia 1 to 1. I tak idąc od tamtąd mamy zwrócić 1 * 2 * 3. Taki wynik dostajemy na końcu.

Nie musimy lubić ani w pełni rozumieć rekurencji. Ważne, że wiemy, że coś takiego istnieje, potrafimy to sobie, jeżeli się wysilimy, rozpisać na kartce i zrozumieć zarówno sam algorytm, czyli nasze podejście do rozwiązania problemu, jak i sposób działania rekurencji. Wprawa nadejdzie z czasem, o ile będziemy z tej rekurencji w ogóle korzystać. Aczkolwiek grzechem byłoby jej nie znać.

Odwróć tekst – iteracyjnie

Piszemy funkcję, aby iteracyjnie (czyli w pętli a nie uciekając się do jakichś sztuczek, jak choćby [::-1]) odwrócić tekst.

Do dzieła. Tym razem zastosujemy pętlę while, bo nie samym for człowiek żyje:

def reverse_text(text):
    rev = ""
    idx = len(text) - 1
    while idx >= 0:
        rev += text[idx]
        idx -= 1
    return rev

print(reverse_text("hello"))
#olleh

A zatem tak – przyjmujemy text jako nasz argument. Zmienna rev to na razie pusty napis „”. Bierzemy indeks ostatniego znaku w naszym tekście, a to jest jego długość -1 (bo zawsze indeksujemy od 0 a zatem długość tekstu jest o 1 większa niż jego ostatni indeks).

Mamy już ostatni indeks. Teraz warunek, że zmienna idx jest większa lub równa 0. Do rev dodajemy element z text o indeksie ostatnim. Zmniejszamy idx o 1 i już mamy indeks przedostatni. I tak idziemy, tak długo, aż idx jest większe lub równe 0 (indeks ostatni). Wtedy go dodajemy, zmniejszamy o 1 i pętla stopuje, -1 nie jest większe ani nawet równe zeru, zaś my dodaliśmy już (wspak) wszystko, co było do dodania, nic tylko zwrócić wynik.

Tak to działa i do rev z hello dopisane jest po koleji o,l,l,e,h. I zwrócony tekst.

Odwracanie tekstu – rekurencyjnie

Odwrócić tekst da się też rekurencyjnie, można to zrobić funkcją, która wywołuje siebie samą. Tak to wygląda:

def reverse(s):
    if s == "":
        return s
    else:
        return reverse(s[1:]) + s[0]
   
             
s = "abc"
print(reverse(s)) 

Warunek brzegowy to pusty string „”. To już daje nam do myślenia, że napis z każdym wywołaniem funkcji będzie skracany, aż do „”.

Dalej mamy zupełnie niepotrzebny else, bo ten przykład jest z internetu. Wywalmy ten else:

def reverse(s):
    if s == "":
        return s
    return reverse(s[1:]) + s[0]


s = "abc"
print(reverse(s)) #cba

Dalej mamy coś ciekawego, bowiem najpierw mamy wywołanie samej siebie a potem znak dodawania (w przypadku tekstów – sklejania tudzież konkatenacji) i element zerowy tekstu.

Działa to tak: przyjmij „abc”. Czy „abc” jest pustym napisem? Nie? To wywołaj się sam na „bc” (wszystko od indeksu 1 do końca) + „a”.

„bc” nie jest pustym napisem, a zatem wywołaj się na „c” (wszystko od indeksu 1 do końca) plus element zerowy „b” po prawej stronie.

Możemy to sobie przeanalizować na kartce, koniec końców ta funkcja zwraca „” +”c” +”b” +”a” co daje nam „cba”, odwrócony tekst. Oczywiście „abc” to tylko taki przykład.

Mam nadzieję, że z tego wpisu coś wynieśliśmy, nawet jeżeli niektóre zagadnienia są problematyczne, powinniśmy znać i rozumieć rekurencję i iterację oraz odrobinę poczuć jak się pracuje z takim bardziej algorytmicznym programowaniem. Od nas zależy, czy chcemy podążać w tym kierunku, czy bardziej pisać programy albo aplikacje internetowe. Ale podstawy podstaw mamy i w razie czego (nie zawsze jest to pisanie samodzielnego kodu, często czytanie cudzego) – jesteśmy w stanie zrozumieć rekurencyjne bądź iteracyjne algorytmy.