Rekurencja i szybkie potęgowanie

Rekurencja to zapis algorytmu, w którym funkcja wywołuje samą siebie dla mniejszego problemu. Ma zawsze dwie części: przypadek bazowy, który kończy wywołania, i krok rekurencyjny, który sprowadza zadanie do mniejszego. Z tej samej idei korzysta szybkie potęgowanie: aⁿ liczy się z potęgi o połowę mniejszej, więc zamiast n mnożeń wystarczy ich kilkanaście.

Na tej stronie są silnia, algorytm Euklidesa, szybkie potęgowanie (rekurencyjne i z pętlą) oraz rekurencyjny rysunek linijki, czyli prosty fraktal. Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta. Krok wchodzi do funkcji, a stos wywołań pokazuje wszystkie aktywne wywołania z ich własnymi zmiennymi.

Przejdź silnię rekurencyjnie krok po kroku

Silnia i NWD rekurencyjnie

Silnia ma naturalną definicję rekurencyjną: 0! = 1! = 1, a n! = n · (n - 1)!. Algorytm Euklidesa też: NWD(a, 0) = a, a NWD(a, b) = NWD(b, a mod b). Obie definicje przepisuje się na Pythona prawie słowo w słowo:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)


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


print(factorial(5), factorial(10))
print(gcd(84, 36), gcd(1000, 7))

120 3628800
12 1

Wywołanie factorial(4) nie może od razu zwrócić wyniku: czeka na factorial(3), które czeka na factorial(2), i tak aż do przypadku bazowego. Dopiero wtedy wyniki wracają w górę: 1, 2, 6, 24. W przeglądarce dobrze to widać w stosie wywołań podczas krokowania.

Szybkie potęgowanie

Zwykłe potęgowanie pętlą wykonuje n mnożeń. Szybkie korzysta z dwóch równości: aⁿ = (aⁿᐟ²)² dla parzystego n oraz aⁿ = (a⁽ⁿ⁻¹⁾ᐟ²)² · a dla nieparzystego. Licznik pokazuje, ile mnożeń naprawdę potrzeba:

multiplications = 0


def power(a, n):
    global multiplications
    if n == 0:
        return 1
    p = power(a, n // 2)
    multiplications += 1
    if n % 2 == 0:
        return p * p
    multiplications += 1
    return p * p * a


print(power(2, 13))
print("mnozen:", multiplications)

8192
mnozen: 7

Wersja z pętlą czyta wykładnik od końca jego zapisu dwójkowego: gdy ostatni bit jest jedynką, mnoży wynik przez bieżące a, a potem podnosi a do kwadratu. Ta sama pętla z resztą z dzielenia po każdym mnożeniu daje potęgowanie modulo, czyli ostatnie cyfry potęg, których nie dałoby się nawet wypisać:

def power_iter(a, n, m):
    result = 1
    a = a % m
    while n > 0:
        if n % 2 == 1:
            result = result * a % m
        a = a * a % m
        n = n // 2
    return result


print(power_iter(3, 20, 10 ** 12))
print(power_iter(7, 2026, 1000))
print(pow(7, 2026, 1000))

3486784401
649
649

Wbudowane pow(a, n, m) w Pythonie robi dokładnie to samo. Na maturze warto umieć napisać tę pętlę samodzielnie: w C++ i w zadaniach z treścią gotowej funkcji nie ma.

Ćwicz: ostatnia cyfra ogromnej potęgi

Fraktal: linijka

Linijka rzędu n to najdłuższa kreska (n znaków) z linijkami rzędu n - 1 po obu stronach. To najprostszy fraktal: każda część wygląda jak całość w mniejszej skali.

def ruler(n):
    if n > 0:
        ruler(n - 1)
        print("-" * n)
        ruler(n - 1)


ruler(3)

-
--
-
---
-
--
-

Każde wywołanie z n > 0 woła funkcję dwa razy, więc linijka rzędu n ma 2ⁿ - 1 kresek. Tak samo rekurencyjnie powstają zbiór Cantora i trójkąt Sierpińskiego w temacie o fraktalach.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Silnia rekurencyjnie

Specyfikacja. Dane: liczba naturalna n. Wynik: n! = 1 · 2 · … · n (0! = 1).

Lista kroków:

1. Wczytaj liczbę n.
2. Oblicz silnia(n) według kroków 3-4 i wypisz wynik.
3. silnia(n): jeśli n ≤ 1, zwróć 1 (przypadek bazowy).
4. W przeciwnym razie zwróć n · silnia(n - 1): funkcja wywołuje samą siebie dla liczby o 1 mniejszej.

Pseudokod:

funkcja silnia(n)
  jeżeli n ≤ 1 to
    zwróć 1
  zwróć n * silnia(n - 1)
wczytaj n
wypisz silnia(n)

Schemat blokowy:

Drzewo wywołań silnia(4). Każde wywołanie czeka na wynik wywołania dla liczby o 1 mniejszej. Przy węźle jest wynik, który funkcja zwraca: wyniki wracają od dołu do góry. Wywołań funkcji: 4.

Algorytm Euklidesa rekurencyjnie

Specyfikacja. Dane: liczby naturalne a i b, a > 0. Wynik: NWD(a, b).

Lista kroków:

1. Wczytaj liczby a i b.
2. Oblicz nwd(a, b) według kroków 3-4 i wypisz wynik.
3. nwd(a, b): jeśli b = 0, zwróć a.
4. W przeciwnym razie zwróć nwd(b, a mod b): para (a, b) zamienia się na (b, reszta z dzielenia a przez b).

Pseudokod:

funkcja nwd(a, b)
  jeżeli b = 0 to
    zwróć a
  zwróć nwd(b, a mod b)
wczytaj a, b
wypisz nwd(a, b)

Schemat blokowy:

Drzewo wywołań nwd(84, 36). Rekurencja Euklidesa nie rozgałęzia się: każde wywołanie woła najwyżej jedno kolejne, a wynik ostatniego wraca bez zmian do pierwszego. Wywołań funkcji: 3.

Szybkie potęgowanie rekurencyjnie

Specyfikacja. Dane: liczba a i liczba naturalna n. Wynik: aⁿ.

Lista kroków:

1. Wczytaj liczby a i n.
2. Oblicz potęga(a, n) według kroków 3-5 i wypisz wynik.
3. potęga(a, n): jeśli n = 0, zwróć 1.
4. Oblicz p = potęga(a, n div 2), czyli potęgę o połowę mniejszą.
5. Jeśli n jest parzyste, zwróć p · p. W przeciwnym razie zwróć p · p · a.

Pseudokod:

funkcja potęga(a, n)
  jeżeli n = 0 to
    zwróć 1
  p ← potęga(a, n div 2)
  jeżeli n mod 2 = 0 to
    zwróć p * p
  w przeciwnym razie
    zwróć p * p * a
wczytaj a, n
wypisz potęga(a, n)

Schemat blokowy:

Drzewo wywołań potęga(2, 13). Wykładnik maleje o połowę w każdym wywołaniu, więc wywołań jest tyle, ile cyfr ma n w systemie dwójkowym, plus jedno dla n = 0. Dla n = 13 = 1101₂ to 5 wywołań zamiast 13 mnożeń. Wywołań funkcji: 5.

Szybkie potęgowanie iteracyjnie

Specyfikacja. Dane: liczba a i liczba naturalna n. Wynik: aⁿ.

Lista kroków:

1. Wczytaj liczby a i n. Ustaw wynik w = 1.
2. Jeśli n = 0, przejdź do kroku 6.
3. Jeśli n jest nieparzyste (ostatnia cyfra dwójkowa n to 1), pomnóż w przez a.
4. Podnieś a do kwadratu i podziel n całkowicie przez 2.
5. Wróć do kroku 2.
6. Wypisz w.

Pseudokod:

wczytaj a, n
w ← 1
dopóki n > 0 wykonuj
  jeżeli n mod 2 = 1 to
    w ← w * a
  a ← a * a
  n ← n div 2
wypisz w

Schemat blokowy:

Linijka (fraktal rekurencyjny)

Specyfikacja. Dane: liczba naturalna n. Wynik: kreski linijki: najdłuższa ma n znaków, po obu stronach linijka rzędu n - 1.

Lista kroków:

1. Wczytaj liczbę n i wykonaj linijka(n) według kroków 2-4.
2. linijka(n): jeśli n = 0, zakończ (nic nie rysuj).
3. Narysuj linijkę rzędu n - 1, wypisz kreskę z n znaków -.
4. Narysuj jeszcze raz linijkę rzędu n - 1.

Pseudokod:

funkcja linijka(n)
  jeżeli n > 0 to
    linijka(n - 1)
    wypisz powtórz("-", n)
    linijka(n - 1)
wczytaj n
linijka(n)

Schemat blokowy:

Drzewo wywołań linijka(2). Każde wywołanie z n > 0 woła linijka(n - 1) dwa razy, więc drzewo jest pełnym drzewem binarnym: dla linijki rzędu n wywołań jest 2ⁿ⁺¹ - 1. Wywołań funkcji: 7.

Najczęstsze błędy

• Brak przypadku bazowego albo zły warunek. factorial(n) bez if n <= 1 woła się bez końca i kończy błędem RecursionError. Sprawdź też, czy każdy krok rekurencyjny zbliża się do przypadku bazowego.
• Liczenie tej samej potęgi dwa razy. power(a, n // 2) * power(a, n // 2) daje dobry wynik, ale wywołań jest tyle, ile mnożeń w zwykłej pętli. Wynik połowy zapisz w zmiennej p i dopiero ją podnieś do kwadratu.
• Reszta z dzielenia tylko na końcu. pow(7, 2026) % 1000 liczy całą ogromną liczbę. W potęgowaniu modulo bierz resztę po każdym mnożeniu.
• Za głęboka rekurencja. factorial(5000) przekracza domyślny limit wywołań w Pythonie. Dla dużych danych wybierz pętlę.

Ćwicz w przeglądarce

W kursie Algorytmy: zakres rozszerzony rekurencja wraca w kilku tematach. Dobre lekcje na start:

• silnia rekurencyjnie,
• wejście i powrót z wywołań rekurencyjnych,
• szybkie potęgowanie rekurencyjnie,
• szybkie potęgowanie iteracyjnie,
• linijka z kreskami różnej długości.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod, schemat blokowy i drzewo wywołań bez wychodzenia z edytora. Iteracyjne wersje z zakresu podstawowego: algorytm Euklidesa i ciąg Fibonacciego.

Dla nauczycieli

Rekurencję najłatwiej zrozumieć, oglądając stos wywołań: krokowanie na rzutniku pokazuje, jak wywołania schodzą w głąb i wracają z wynikami. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć. Pełna lista algorytmów: algorytmy.