Rekursja – dziel i zwyciężaj

Home
C_Apps
D_Apps
M_Apps
W_Apps
D_Base
IT

Rekursja (ang. recursion) to sytuacja, w której funkcja wywołuje samą siebie, aż do osiągnięcia warunku stopu.

Przykład prosty: obliczanie silni n!

def silnia(n):
    if n == 0:
        return 1        # warunek stopu
    else:
        return n * silnia(n-1)

Na czym polega strategia „dziel i zwyciężaj”?

To sposób rozwiązywania problemów, który działa według schematu:

  1. Podziel (Divide) – duży problem dzielimy na mniejsze, prostsze podproblemy.
  2. Rozwiąż (Conquer) – rozwiązujemy każdy podproblem (najczęściej rekurencyjnie).
  3. Połącz (Combine) – składamy rozwiązania podproblemów w całość.

1. Wyszukiwanie binarne – najprostszy przykład dziel i zwyciężaj

Problem
Masz posortowaną listę liczb:

[3, 6, 9, 12, 15, 18, 21]

Chcesz sprawdzić, czy jest tam liczba 15.

Myślenie „dziel i zwyciężaj”

  1. Nie przeszukujemy wszystkiego po kolei.
  2. Dzielimy listę na pół i sprawdzamy środkowy element.
    • Jeśli to szukana liczba → koniec.
    • Jeśli szukana liczba jest mniejsza od środkowego → wystarczy szukać w lewej połowie.
    • Jeśli jest większa → szukamy w prawej połowie.
  3. Powtarzamy ten sam pomysł aż znajdziemy lub zostanie pusta lista.

Rysunek w głowie (dla liczby 15)

Lista: [3, 6, 9, 12, 15, 18, 21]

  1. Środek → 12. 15 > 12, więc szukamy w prawej części [15, 18, 21].
  2. Środek → 18. 15 < 18, więc szukamy w lewej części [15].
  3. Środek → 15. Bingo! Znalezione.

Przykład w Python

def binarne_szukaj(tab, x, lewy, prawy):
    # jeśli lewy > prawy, to zakres pusty -> brak elementu
    if lewy > prawy:
        return -1  

    srodek = (lewy + prawy) // 2  # dzielimy na pół

    if tab[srodek] == x:          # trafiliśmy!
        return srodek
    elif tab[srodek] > x:         # szukamy w lewej połowie
        return binarne_szukaj(tab, x, lewy, srodek - 1)
    else:                         # szukamy w prawej połowie
        return binarne_szukaj(tab, x, srodek + 1, prawy)


# przykład użycia
lista = [3, 6, 9, 12, 15, 18, 21]
print(binarne_szukaj(lista, 15, 0, len(lista)-1))  # -> 4
print(binarne_szukaj(lista, 7, 0, len(lista)-1))   # -> -1

Dlaczego to „dziel i zwyciężaj”?

  • Dziel: za każdym razem bierzemy tylko połowę listy.
  • Zwyciężaj: zmniejszamy problem i rozwiązujemy go tak samo (rekurencja).
  • Efekt: zamiast sprawdzać 7 elementów po kolei, sprawdziliśmy tylko 3.

Definicja sortowania przez scalanie (MergeSort)

Sortowanie przez scalanie to algorytm sortowania oparty na metodzie dziel i zwyciężaj.

Polega na tym, że:

  1. Dzielimy tablicę na dwie połowy.
  2. Sortujemy rekurencyjnie każdą połowę.
  3. Scalamy (łączymy) obie posortowane listy w jedną posortowaną całość.

Cechy algorytmu

  • Zawsze działa w czasie O(n log n), niezależnie od danych wejściowych.
  • Wymaga dodatkowej pamięci na proces scalania (O(n)).
  • Jest stabilny – zachowuje kolejność elementów równych.

Zadanie

Posortuj listę wyników testu uczniów:
[42, 17, 23, 17, 58, 34] używając algorytmu sortowania przez scalanie.

Schemat postępowania

  1. Dziel tablicę na dwie części. [42, 17, 23] oraz [17, 58, 34]
  2. Sortuj rekurencyjnie każdą część.
    • [42, 17, 23] → dzielimy na [42] i [17, 23] [17, 23] → dzielimy na [17] i [23] → scalanie = [17, 23] scalanie [42] i [17, 23] = [17, 23, 42]
    • [17, 58, 34] → dzielimy na [17] i [58, 34] [58, 34] → [58] i [34] → scalanie = [34, 58] scalanie [17] i [34, 58] = [17, 34, 58]
  3. Scal obie posortowane połowy: [17, 23, 42] i [17, 34, 58] → [17, 17, 23, 34, 42, 58]

Wynik

Posortowana lista:
[17, 17, 23, 34, 42, 58]

def scalaj(lewa, prawa):
    wynik = []
    i = j = 0
    # dopóki w obu listach są elementy
    while i < len(lewa) and j < len(prawa):
        if lewa[i] <= prawa[j]:
            wynik.append(lewa[i])
            i += 1
        else:
            wynik.append(prawa[j])
            j += 1
    # dokładamy resztę (jedna z list mogła się skończyć wcześniej)
    wynik.extend(lewa[i:])
    wynik.extend(prawa[j:])
    return wynik

def mergesort(tab):
    if len(tab) <= 1:  # warunek stopu
        return tab
    srodek = len(tab) // 2
    lewa = mergesort(tab[:srodek])   # rekurencyjnie sortujemy lewą
    prawa = mergesort(tab[srodek:])  # rekurencyjnie sortujemy prawą
    return scalaj(lewa, prawa)       # scalanie

# przykład
punkty = [42, 17, 23, 17, 58, 34]
print("Posortowane:", mergesort(punkty))
  • Jak działa MergeSort w skrócie

    Dzielimy listę na połowy, aż zostaną pojedyncze elementy.
    – pojedynczy element jest z definicji posortowany.
    Scalamy dwie posortowane listy w jedną większą posortowaną.
    – tutaj faktycznie porównujemy elementy „z lewej” i „z prawej”.

    Sam proces scalania
    Mamy dwie posortowane listy:
    [17, 23, 42] (lewa)
    [17, 34, 58] (prawa)

    Scalanie wygląda tak:

    Porównuję pierwszy element lewej (17) z pierwszym elementem prawej (17).
    – są równe → biorę np. z lewej. Wynik: [17].
    Znowu porównuję 23 z 17.
    – 17 < 23 → biorę 17 z prawej. Wynik: [17, 17].
    Teraz porównuję 23 z 34.
    – 23 < 34 → biorę 23. Wynik: [17, 17, 23].
    Porównuję 42 z 34.
    – 34 < 42 → biorę 34. Wynik: [17, 17, 23, 34].
    Porównuję 42 z 58.
    – 42 < 58 → biorę 42. Wynik: [17, 17, 23, 34, 42].
    Lewa lista się skończyła → dokładam resztę prawej [58].
    Ostateczny wynik: [17, 17, 23, 34, 42, 58].

3. BubbleSort – sortowanie bąbelkowe

Sortowanie bąbelkowe to jeden z najprostszych algorytmów sortowania.
Polega na wielokrotnym przechodzeniu przez tablicę i porównywaniu sąsiednich elementów.
Jeśli są w złej kolejności – zamieniamy je miejscami.
Największe elementy „wypływają” stopniowo na koniec tablicy – jak bąbelki powietrza w wodzie (stąd nazwa).

Schemat działania krok po kroku

Weźmy tablicę:

[5, 3, 8, 4, 2]

  1. Pierwsze przejście (od lewej do prawej):
    • Porównuję 5 i 3 → zamiana → [3, 5, 8, 4, 2]
    • Porównuję 5 i 8 → bez zamiany → [3, 5, 8, 4, 2]
    • Porównuję 8 i 4 → zamiana → [3, 5, 4, 8, 2]
    • Porównuję 8 i 2 → zamiana → [3, 5, 4, 2, 8]
    Największa liczba (8) jest już na końcu.
  2. Drugie przejście:
    • Porównuję 3 i 5 → bez zamiany → [3, 5, 4, 2, 8]
    • Porównuję 5 i 4 → zamiana → [3, 4, 5, 2, 8]
    • Porównuję 5 i 2 → zamiana → [3, 4, 2, 5, 8]
    Teraz druga największa (5) „ustawiła się” na przedostatnim miejscu.
  3. Trzecie przejście:
    • Porównuję 3 i 4 → bez zamiany → [3, 4, 2, 5, 8]
    • Porównuję 4 i 2 → zamiana → [3, 2, 4, 5, 8]
  4. Czwarte przejście:
    • Porównuję 3 i 2 → zamiana → [2, 3, 4, 5, 8]

Tablica jest posortowana.

[2, 3, 4, 5, 8]

def bubble_sort(tab):
    n = len(tab)
    for i in range(n-1):  # powtarzamy n-1 razy
        for j in range(n-1-i):  # za każdym razem o 1 porównanie mniej
            if tab[j] > tab[j+1]:
                # zamiana miejscami
                tab[j], tab[j+1] = tab[j+1], tab[j]
    return tab

# przykład
dane = [5, 3, 8, 4, 2]
print("Posortowane:", bubble_sort(dane))

**
W MergeSort podczas scalania zawsze patrzysz na pierwszy element lewej listy i pierwszy element prawej listy i wybierasz mniejszy z nich.

1. [38, 27, 43, 3, 9, 82, 10, 50]
2. [38, 27, 43, 3]     [9, 82, 10, 50]
3. [38, 27]   [43, 3]     [9, 82]   [10, 50]
4. [38] [27]   [43] [3]     [9] [82]   [10] [50]

5. Scalanie po dwa elementy

scal [10] i [50] → [10, 50]
scal [38] i [27] → [27, 38]
scal [43] i [3] → [3, 43]
scal [9] i [82] → [9, 82]. -> wynik scalania po tej rundzie [27, 38]   [3, 43]     [9, 82]   [10, 50]

6.  Scalanie większych fragmentów

scal [9, 82] i [10, 50] → [9, 10, 50, 82]
scal [27, 38] i [3, 43] → [3, 27, 38, 43] -> wynik scalania po tej rundzie [3, 27, 38, 43]     [9, 10, 50, 82]

7. Ostatnie scalanie
scal [3, 27, 38, 43] i [9, 10, 50, 82] → [3, 9, 10, 27, 38, 43, 50, 82]