Rekurencja – Python

Rekurencja to sytuacja, w której funkcja w programie wywołuje samą siebie, żeby rozwiązać mniejszą wersję tego samego problemu.

Każda funkcja rekurencyjna ma dwa kluczowe elementy:

• Warunek końcowy (bazowy) – miejsce, w którym mówimy: „dalej już nie liczymy, tutaj znamy odpowiedź”.
• Wywołanie rekurencyjne – linijka, w której funkcja „woła samą siebie”, ale z prostszym argumentem (np. mniejszą liczbą).

Jeśli nie ma warunku końcowego → program nigdy się nie zatrzyma (będzie wywoływał sam siebie w nieskończoność).

---

1. Czym jest rekurencja?

Intuicyjnie możesz myśleć o rekurencji jak o serii „zleceń”: funkcja nie liczy wszystkiego od razu, tylko mówi: „najpierw policz mi wersję prostszą, a ja dokończę”.

Przykład 1: Silnia

Silnia liczby n (zapis: n!) to iloczyn wszystkich liczb od 1 do n:

• 0! = 1
• 5! = 5 × 4 × 3 × 2 × 1 = 120

def silnia(n):
    if n == 0:        # 1. jeśli n to 0...
        return 1      # 2. ...zwracamy 1 i kończymy

    return n * silnia(n - 1)  # 3. inaczej: n razy silnia z (n-1)


# przykłady:
print(silnia(0))  # 1
print(silnia(4))  # 24
print(silnia(6))  # 720

Wyjaśnienie:

• if n == 0: – pytamy: „Czy dotarliśmy do najprostszego przypadku?” (silnia z 0 jest z definicji równa 1).
• return 1 – jeśli tak, to kończymy i zwracamy 1 (nie wywołujemy już funkcji dalej).
• return n * silnia(n - 1) – w pozostałych przypadkach mówimy: „policz silnię poprzedniej liczby i pomnóż przez n”.

Gdy wywołamy silnia(4), w środku powstaje łańcuch:

4 * silnia(3) → 4 * (3 * silnia(2)) → 4 * (3 * (2 * silnia(1))) → … aż dojdziemy do silnia(0), które zwraca 1 i wszystko się „rozplątuje”.

Przykład 2: Odliczanie w dół

def odliczanie(n):
    if n == 0:                 # 1. jeśli n to 0...
        print("Start!")        # 2. ...drukujemy komunikat
        return                 # 3. kończymy funkcję

    print(n)                   # 4. wypisz aktualną liczbę
    odliczanie(n - 1)          # 5. wywołaj siebie z n-1


odliczanie(5)

Wyjaśnienie:

• Funkcja kolejno wypisze: 5, 4, 3, 2, 1, a na końcu Start!.
• Najpierw drukuje obecną liczbę (print(n)), potem woła samą siebie z liczbą mniejszą o 1 (n - 1).
• Gdy dotrze do n == 0, zamiast wywoływać się dalej, wypisze „Start!” i zakończy działanie.

Przykład 3: Suma liczb od 1 do n

def suma_do_n(n):
    if n == 1:          # 1. dla 1 wynik jest oczywisty
        return 1

    return n + suma_do_n(n - 1)


print(suma_do_n(5))  # 1+2+3+4+5 = 15

Wyjaśnienie:

• if n == 1: – najprostszy przypadek: suma od 1 do 1 to po prostu 1.
• return n + suma_do_n(n - 1) – żeby policzyć sumę do 5, dodajemy 5 do sumy do 4; żeby policzyć sumę do 4, dodajemy 4 do sumy do 3 itd.

W środku tworzy się wyrażenie: 5 + (4 + (3 + (2 + 1))).

Ćwiczenie 10.1

• Wskaż w przykładach 1–3:
  • warunek końcowy,
  • wywołanie rekurencyjne.
• Co się stanie, jeśli w funkcji silnia usuniesz warunek if n == 0?
• Opisz własnym przykładem rekurencję z życia (np. budzenie domowników, przekazywanie informacji po łańcuszku).

---

2. Rekurencyjna definicja ciągu

Ciąg rekurencyjny to taki, w którym każdy wyraz można obliczyć na podstawie poprzedniego (lub kilku poprzednich).

Przykład ciągu arytmetycznego:

• a₁ = 7
• aₙ = aₙ₋₁ + 3

Można to interpretować jako konto bankowe, na które co miesiąc dopłacasz stałą kwotę.

Przykład 1: Ciąg arytmetyczny (dodajemy stałą liczbę)

def wyraz_ciagu_arytm(a1, d, n):
    if n == 1:             # 1. pierwszy wyraz znamy
        return a1

    return wyraz_ciagu_arytm(a1, d, n - 1) + d


# a1 = 7, d = 3
for i in range(1, 6):
    print(f"a_{i} =", wyraz_ciagu_arytm(7, 3, i))

Wyjaśnienie:

• Dla n == 1 nie liczymy nic – po prostu zwracamy wartość początkową a1.
• Dla n > 1 mówimy: „oblicz poprzedni wyraz i dodaj różnicę d”.
• Przykład: a_5 = a_4 + 3, a_4 = a_3 + 3 itd.

Przykład 2: Ciąg geometryczny (mnożenie przez stały współczynnik)

Ciąg geometryczny:

• a₁ = a1
• aₙ = q · aₙ₋₁

def wyraz_ciagu_geom(a1, q, n):
    if n == 1:          # jeśli to pierwszy wyraz
        return a1

    return q * wyraz_ciagu_geom(a1, q, n - 1)


# przykład: a1=2, q=3
for i in range(1, 6):
    print(f"b_{i} =", wyraz_ciagu_geom(2, 3, i))

Wyjaśnienie:

• Tu zamiast dodawać stałą liczbę, mnożymy przez stały współczynnik q.
• b_1 = 2, b_2 = 2·3 = 6, b_3 = 6·3 = 18 itd.
• Rekurencja: „oblicz poprzedni wyraz i pomnóż przez q”.

Przykład 3: „Oszczędzanie” – saldo konta

Załóżmy:

• początkowo masz 1000 zł,
• co miesiąc dopłacasz 200 zł,
• chcemy znać saldo w miesiącu n.

def saldo(miesiac, poczatek=1000, wplata=200):
    if miesiac == 1:           # pierwszy miesiąc – znamy saldo
        return poczatek

    return saldo(miesiac - 1, poczatek, wplata) + wplata


for m in range(1, 7):
    print(f"Miesiąc {m}: {saldo(m)} zł")

Wyjaśnienie:

• W 1. miesiącu saldo to po prostu kwota początkowa poczatek.
• Każdy kolejny miesiąc: saldo z poprzedniego miesiąca + wpłata wplata.
• Rekurencja odzwierciedla dokładnie to, co policzyłbyś „na kartce”: miesiąc po miesiącu.

Ćwiczenie 10.2

• Dany jest ciąg: a₁ = 7, aₙ = aₙ₋₁ + 3. Oblicz ręcznie a₂, a₃, a₄, a₅.
• Uruchom przykład 1 w Pythonie i sprawdź, czy wyniki zgadzają się z obliczeniami.
• Podaj przykład ciągu malejącego (dobierz d < 0) oraz ciągu stałego (dowolne a₁, ale d = 0).

---

3. Ciąg Fibonacciego

Ciąg Fibonacciego jest zdefiniowany tak:

• F(0) = 0
• F(1) = 1
• F(n) = F(n−1) + F(n−2) dla n ≥ 2

Każda liczba to suma dwóch poprzednich. Występuje w naturze (spirale nasion, liczba płatków kwiatów), w informatyce i w sztuce.

Przykład 1: Podstawowa funkcja fib

def fib(n):
    if n == 0:
        return 0          # znamy od razu
    if n == 1:
        return 1          # też znamy

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


for i in range(8):
    print(f"F({i}) =", fib(i))

Wyjaśnienie:

• Dwa najprostsze przypadki – 0 i 1 – zwracamy bez liczenia.
• Dla pozostałych n mówimy: „policz dwie poprzednie liczby i dodaj je”.

Wywołania układają się w „drzewko zadań”: żeby policzyć F(5), musisz policzyć F(4) i F(3); żeby policzyć F(4), potrzebujesz F(3) i F(2) itd.

Przykład 2: Lista pierwszych k liczb Fibonacciego

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)


def fib_lista(k):
    lista = []
    for i in range(k):
        lista.append(fib(i))  # dopisujemy kolejne F(i) do listy
    return lista


print(fib_lista(8))   # [0, 1, 1, 2, 3, 5, 8, 13]

Wyjaśnienie:

• fib liczy pojedynczą liczbę Fibonacciego.
• fib_lista(k) tworzy pustą listę i po kolei dopisuje fib(0), fib(1), ..., fib(k-1).
• W efekcie otrzymujemy cały ciąg w jednym obiekcie (liście).

Przykład 3: Rekurencyjne wypisywanie ciągu Fibonacciego

def wypisz_fib(n):
    if n == 0:
        print(0)
        return
    if n == 1:
        print(0)
        print(1)
        return

    # najpierw wypisz poprzednie liczby
    wypisz_fib(n - 1)

    # potem wypisz F(n)
    print(fib(n))


def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)


wypisz_fib(6)

Wyjaśnienie:

• Funkcja wypisz_fib używa rekurencji nie do liczenia, lecz do wypisywania kolejnych liczb.
• Najpierw wywołuje samą siebie z n-1, aby wypisać wszystkie wcześniejsze elementy.
• Na końcu dopisuje F(n), korzystając z funkcji fib.

Ćwiczenie 10.3

• Uzupełnij tabelę:

  n	0	1	2	3	4	5	6	7
  F(n)

• Oblicz ręcznie F(7), wypisując wszystkie potrzebne wcześniejsze F(n).
• Sprawdź wynik w Pythonie, korzystając z funkcji fib.
• Zmodyfikuj pętlę for tak, aby wypisywała tylko liczby Fibonacciego o parzystych indeksach (0, 2, 4, 6...).

---

10.4. Rekurencyjny algorytm Euklidesa (NWD)

Algorytm Euklidesa oblicza największy wspólny dzielnik (NWD) dwóch liczb całkowitych.

Idea:

1. Dzielimy liczbę a przez b, bierzemy resztę.
2. Tworzymy nową parę liczb: (b, reszta).
3. Powtarzamy, aż reszta będzie równa 0.
4. Liczba, która wtedy zostanie, jest NWD.

10.4 – Przykład 1: Podstawowa funkcja nwd

def nwd(a, b):
    if b == 0:             # gdy dzielimy "na czysto"
        return a           # a jest największym dzielnikiem

    return nwd(b, a % b)   # w przeciwnym razie: zamień role liczb


print(nwd(48, 18))   # 6
print(nwd(84, 30))   # 6
print(nwd(30, 21))   # 3

Wyjaśnienie:

• b pełni rolę dzielnika.
• Jeśli b == 0, to znaczy, że poprzednim razem dzieliliśmy „na czysto” – liczba a jest naszym największym wspólnym dzielnikiem.
• W przeciwnym razie wywołujemy funkcję ponownie z parą (b, a % b), czyli „dzielnikiem i resztą”.

10.4 – Przykład 2: Skracanie ułamka przy użyciu NWD

def nwd(a, b):
    if b == 0:
        return a
    return nwd(b, a % b)


def skroc_ulamek(licznik, mianownik):
    d = nwd(licznik, mianownik)        # największy wspólny dzielnik
    return licznik // d, mianownik // d


print(skroc_ulamek(42, 56))   # (3, 4)
print(skroc_ulamek(36, 60))   # (3, 5)
print(skroc_ulamek(75, 105))  # (5, 7)

Wyjaśnienie:

• Najpierw znajdujemy NWD licznika i mianownika.
• Potem dzielimy licznik i mianownik przez tę samą liczbę d.
• Otrzymujemy ułamek skrócony – równoważny, ale z mniejszymi liczbami.

10.4 – Przykład 3: Sprawdzenie, czy liczby są „względnie pierwsze”

Liczby są względnie pierwsze, gdy ich NWD = 1 (nie mają wspólnych dzielników poza 1).

def nwd(a, b):
    if b == 0:
        return a
    return nwd(b, a % b)


def wzglednie_pierwsze(a, b):
    return nwd(a, b) == 1


print(wzglednie_pierwsze(8, 15))   # True (względnie pierwsze)
print(wzglednie_pierwsze(12, 18))  # False (NWD=6)
print(wzglednie_pierwsze(7, 20))   # True

Wyjaśnienie:

• Funkcja wzglednie_pierwsze wykorzystuje „w tle” algorytm Euklidesa.
• Jeśli nwd(a, b) == 1, oznacza to, że liczby nie mają wspólnych dzielników większych niż 1.
• To pojęcie jest ważne m.in. w kryptografii (np. w algorytmach szyfrowania).

Ćwiczenie 10.4

• Oblicz ręcznie NWD(84, 30), wykonując kolejne dzielenia z resztą.
• Sprawdź wynik funkcją nwd(84, 30) w Pythonie.
• Skróć ułamki: 36/60 oraz 75/105, korzystając z programu.
• Rozszerz funkcję skroc_ulamek tak, aby pobierała licznik i mianownik z klawiatury (użyj input()).

---

Podsumowanie

Rekurencja pozwala dzielić duże problemy na mniejsze i rozwiązywać je krok po kroku. Jest kluczowa w algorytmice, sortowaniu, przetwarzaniu drzew (np. folderów na dysku), operacjach na ciągach liczbowych oraz w wielu algorytmach matematycznych.

Rekurencja pomaga w…	Przykłady
przetwarzaniu struktur „w głąb”	katalogi i podkatalogi, drzewa genealogiczne
rozwiązywaniu dużych problemów przez dzielenie ich na mniejsze	sortowanie szybsze niż proste metody „szkolne”, dzielenie przedziałów
modelowaniu natury i zjawisk	fraktale, wzrost roślin, spirale w naturze
matematyce obliczeniowej	NWD, silnia, ciągi liczbowe (np. Fibonacciego)

Im lepiej zrozumiesz rekurencję, tym łatwiej będzie Ci pracować z bardziej zaawansowanymi algorytmami w przyszłości.