Recursion

You can run every example right here, then edit the code and see what changes. Your code runs only in this browser, in an isolated environment with no access to the internet or your account.

Rekurzia znamená, že funkcia volá samu seba. Znie to zvláštne, ale veľa problémov sa dá prirodzene opísať práve takto: veľký problém vyriešime pomocou toho istého problému, len menšieho. Faktoriál 5 je 5 krát faktoriál 4; súčet cifier čísla 4728 je 8 plus súčet cifier čísla 472. Kľúčom je vždy vedieť, kedy sa zastaviť.

Čo sa naučíš

napísať rekurzívnu funkciu so základným prípadom a rekurzívnym krokom,
pochopiť, prečo rekurzia bez základného prípadu skončí chybou RecursionError,
sledovať priebeh rekurzie (zásobník volaní, poradie výpisov),
riešiť rekurziou klasické úlohy: súčet cifier, mocninu, NSD, Hanojské veže.

1Rekurzívna funkcia

Faktoriál sa dá definovať aj takto: 0! = 1 a n! = n · (n − 1)! pre n > 0. Túto definíciu môžeme priamo prepísať do Pythonu:

Python

def faktorial(n):

if n == 0: # základný prípad

return 1

return n * faktorial(n - 1) # rekurzívny krok

print(faktorial(5))

print([faktorial(i) for i in range(8)])

Výstup:

120
[1, 1, 2, 6, 24, 120, 720, 5040]

Každá rekurzívna funkcia má dve časti:

Základný prípad – najjednoduchší vstup, pre ktorý výsledok poznáme hneď, bez ďalšieho volania (n == 0).
Rekurzívny krok – výsledok vyjadríme pomocou volania tej istej funkcie pre menší problém (n - 1).

Rekurzívny krok musí problém zakaždým zmenšiť tak, aby sa raz dostal k základnému prípadu.

2Základný prípad

Čo sa stane, keď základný prípad chýba?

Python

def odpocitaj(n):

print(n)

odpocitaj(n - 1)

odpocitaj(3)

Výstup (program skončí chybou):

3
2
1
0
…
Traceback (most recent call last):
  File "program.py", line 5, in <module>
    odpocitaj(3)
  File "program.py", line 3, in odpocitaj
    odpocitaj(n - 1)
  File "program.py", line 3, in odpocitaj
    odpocitaj(n - 1)
  File "program.py", line 3, in odpocitaj
    odpocitaj(n - 1)
  [Previous line repeated 992 more times]
  File "program.py", line 2, in odpocitaj
    print(n)
RecursionError: maximum recursion depth exceeded while calling a Python object

Funkcia by sa volala donekonečna: 3, 2, 1, 0, −1, −2… Python preto počet vnorených volaní obmedzuje (predvolene asi na 1000) a po jeho prekročení vyvolá RecursionError. (Z dlhého výpisu sú tu ukázané iba začiatok a koniec.) Oprava – pridáme základný prípad:

Python

def odpocitaj(n):

if n == 0:

print("Štart!")

return

print(n)

odpocitaj(n - 1)

odpocitaj(3)

Výstup:

3
2
1
Štart!

Rovnako zle dopadne aj funkcia, ktorej krok problém nezmenšuje (faktorial(n) volá faktorial(n)) alebo ho zmenšuje tak, že základný prípad „preskočí“ (faktorial(-1) pri podmienke n == 0).

3Priebeh rekurzie

Pri každom volaní funkcie si Python založí nový „záznam“ s jej lokálnymi premennými. Záznamy sa ukladajú na seba ako taniere – hovoríme o zásobníku volaní. Volanie faktorial(3) prebieha takto:

faktorial(3)
│ potrebuje 3 * faktorial(2)
│ │ potrebuje 2 * faktorial(1)
│ │ │ potrebuje 1 * faktorial(0)
│ │ │ │ faktorial(0) vráti 1         ← základný prípad
│ │ │ vráti 1 * 1 = 1
│ │ vráti 2 * 1 = 2
│ vráti 3 * 2 = 6
výsledok 6

Najprv ide rekurzia „dole“ až k základnému prípadu, potom sa výsledky vracajú „hore“ a postupne sa skladajú.

3.1Výpis pred volaním a po ňom

Príkaz pred rekurzívnym volaním sa vykoná cestou dole, príkaz za ním až cestou späť – v opačnom poradí:

Python

def dole_hore(n):

if n == 0:

return

print("dole", n)

dole_hore(n - 1)

print("hore", n)

dole_hore(3)

Výstup:

dole 3
dole 2
dole 1
hore 1
hore 2
hore 3

Takto sa dá napríklad vypísať číslo odzadu alebo text obrátene bez cyklu:

Python

def odzadu(s):

if s == "":

return ""

return odzadu(s[1:]) + s[0]

print(odzadu("rekurzia"))

Výstup:

aizruker

3.2Sledovanie hĺbky

Keď chceš rekurzii porozumieť, pridaj do funkcie parameter s hĺbkou a odsadzuj výpis:

Python

def sucet(n, hlbka=0):

print(" " * hlbka + f"sucet({n})")

if n == 0:

return 0

vysledok = n + sucet(n - 1, hlbka + 1)

print(" " * hlbka + f"→ {vysledok}")

return vysledok

sucet(3)

Výstup:

sucet(3)
  sucet(2)
    sucet(1)
      sucet(0)
    → 1
  → 3
→ 6

4Rekurzívne algoritmy

4.1Súčet cifier

Súčet cifier čísla je jeho posledná cifra plus súčet cifier čísla bez poslednej cifry. Jednociferné číslo je samo sebe súčtom:

Python

def sucet_cifier(n):

if n < 10:

return n

return n % 10 + sucet_cifier(n // 10)

print(sucet_cifier(4728))

Výstup:

4.2Mocnina

aⁿ = a · aⁿ⁻¹ a a⁰ = 1. Rýchlejšia verzia využíva, že pri párnom n je aⁿ = (a^(n/2))²; počet volaní sa tak zmenší z n na približne log₂ n:

Python

def mocnina(a, n):

if n == 0:

return 1

return a * mocnina(a, n - 1)

def rychla_mocnina(a, n):

if n == 0:

return 1

polovica = rychla_mocnina(a, n // 2)

if n % 2 == 0:

return polovica * polovica

return a * polovica * polovica

print(mocnina(2, 10), rychla_mocnina(2, 10), rychla_mocnina(3, 13))

Výstup:

1024 1024 1594323

4.3Najväčší spoločný deliteľ

Euklidov algoritmus je prirodzene rekurzívny: NSD(a, 0) = a a NSD(a, b) = NSD(b, a mod b):

Python

def nsd(a, b):

if b == 0:

return a

return nsd(b, a % b)

print(nsd(84, 126))

Výstup:

4.4Palindróm

Text je palindróm, ak sa jeho prvý a posledný znak zhodujú a palindrómom je aj to, čo je medzi nimi. Prázdny text a text s jedným znakom sú palindrómy:

Python

def je_palindrom(s):

if len(s) <= 1:

return True

if s[0] != s[-1]:

return False

return je_palindrom(s[1:-1])

for slovo in ["kajak", "radar", "python", "a"]:

print(slovo, je_palindrom(slovo))

Výstup:

kajak True
radar True
python False
a True

4.5Fibonacciho čísla a cena opakovaných výpočtov

F(1) = F(2) = 1 a F(n) = F(n − 1) + F(n − 2). Priamy rekurzívny zápis je krásne krátky, ale veľmi pomalý: tie isté hodnoty počíta znova a znova (F(5) volá F(4) aj F(3), F(4) opäť F(3)…). Spočítajme volania:

Python

volania = 0

def fib(n):

global volania

volania += 1

if n <= 2:

return 1

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

for n in [10, 20, 25]:

volania = 0

print(f"fib({n}) = {fib(n)}, počet volaní: {volania}")

Výstup:

fib(10) = 55, počet volaní: 109
fib(20) = 6765, počet volaní: 13529
fib(25) = 75025, počet volaní: 150049

Počet volaní rastie takmer dvojnásobne s každým ďalším n. Cyklom (téma Cykly) sa F(n) vypočíta v n krokoch. Rekurziu preto používaj tam, kde sa podproblémy neopakujú – alebo si už vypočítané výsledky pamätaj (napríklad v slovníku).

4.6Hanojské veže

Na prvom kolíku je veža z n diskov (väčšie dole). Treba ju presunúť na tretí kolík; naraz sa smie presúvať iba jeden disk a nikdy nesmie ležať väčší disk na menšom. Riešenie je typicky rekurzívne:

presuň n − 1 diskov z prvého kolíka na pomocný,
presuň najväčší disk na cieľový kolík,
presuň n − 1 diskov z pomocného kolíka na cieľový.

Python

def hanoj(n, odkial, kam, pomocny):

if n == 0:

return

hanoj(n - 1, odkial, pomocny, kam)

print(f"disk {n}: {odkial} → {kam}")

hanoj(n - 1, pomocny, kam, odkial)

hanoj(3, "A", "C", "B")

Výstup:

disk 1: A → C
disk 2: A → B
disk 1: C → B
disk 3: A → C
disk 1: B → A
disk 2: B → C
disk 1: A → C

Na n diskov treba 2ⁿ − 1 presunov – pre 3 disky 7, pre 64 diskov viac, než by stihol ktokoľvek za celý život.

4.7Všetky možnosti: dvojkové reťazce

Rekurzia sa výborne hodí na vymenovanie všetkých možností: na každom mieste skúsime 0 aj 1 a pre zvyšok zavoláme tú istú funkciu.

Python

def vsetky(n, zaciatok=""):

if n == 0:

print(zaciatok, end=" ")

return

vsetky(n - 1, zaciatok + "0")

vsetky(n - 1, zaciatok + "1")

vsetky(3)

print()

Výstup:

000 001 010 011 100 101 110 111

4.8Súčet čísel vo vnorenom zozname

Zoznam môže obsahovať ďalšie zoznamy, tie zase ďalšie… Rekurzia si s ľubovoľnou hĺbkou vnorenia poradí ľahko:

Python

def sucet(z):

spolu = 0

for prvok in z:

if isinstance(prvok, list):

spolu += sucet(prvok) # vnorený zoznam – rekurzia

else:

spolu += prvok

return spolu

print(sucet([1, [2, 3], [4, [5, 6, [7]]], 8]))

Výstup:

isinstance(prvok, list) zisťuje, či je prvok zoznam.

5Rekurzia alebo cyklus?

Každú rekurziu možno prepísať na cyklus a naopak.
Rekurzia je prirodzená pri problémoch, ktoré sa rozpadajú na menšie problémy rovnakého druhu: vnorené štruktúry, stromy, „rozdeľ a panuj“ (binárne vyhľadávanie, triedenie zlučovaním), vymenovanie všetkých možností.
Cyklus býva rýchlejší a nemá obmedzenie hĺbky. Na jednoduché opakovanie (súčet 1 až n, faktoriál) je v Pythone lepší cyklus.

6Časté chyby

Chýbajúci alebo nedosiahnuteľný základný prípad → RecursionError.
Krok nezmenšuje problém (volanie s rovnakým argumentom).
Zabudnutý return pri rekurzívnom volaní: faktorial(n - 1) bez return výsledok zahodí a funkcia vráti None.

Python

def faktorial(n):

if n == 0:

return 1

n * faktorial(n - 1) # chýba return

print(faktorial(3))

Výstup (program skončí chybou):

Traceback (most recent call last):
  File "program.py", line 6, in <module>
    print(faktorial(3))
          ^^^^^^^^^^^^
  File "program.py", line 4, in faktorial
    n * faktorial(n - 1)        # chýba return
        ^^^^^^^^^^^^^^^^
  File "program.py", line 4, in faktorial
    n * faktorial(n - 1)        # chýba return
    ~~^~~~~~~~~~~~~~~~~~
TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

Výnimka vznikla až v hĺbke: faktorial(1) vrátil None a výraz 2 * None je chyba.

Príliš veľký vstup: faktorial(5000) prekročí limit hĺbky – použi cyklus.

Zhrnutie

Rekurzívna funkcia volá samu seba; má základný prípad (bez volania) a rekurzívny krok (menší problém).
Bez dosiahnuteľného základného prípadu vznikne RecursionError (limit asi 1000 volaní).
Volania tvoria zásobník: cestou dole sa volá, cestou hore sa výsledky skladajú; príkazy za volaním sa vykonajú v opačnom poradí.
Klasika: faktoriál, súčet cifier, mocnina, NSD, palindróm, Hanojské veže, vymenovanie možností.
Pri opakujúcich sa podproblémoch (naivný Fibonacci) je rekurzia veľmi pomalá.

Úlohy na precvičenie

Napíš rekurzívnu funkciu, ktorá vráti súčet čísel od 1 po n.
Napíš rekurzívnu funkciu pocet_cifier(n).
Napíš rekurzívnu funkciu, ktorá vypíše čísla od n po 1 a potom späť od 1 po n.
Napíš rekurzívnu funkciu, ktorá vráti maximum zoznamu (maximum z prvého prvku a maxima zvyšku).
Uprav Fibonacciho funkciu tak, aby si vypočítané hodnoty pamätala v slovníku, a porovnaj počet volaní.
Vypíš všetky slová dĺžky 3 z písmen a, b, c (rekurzívne, ako dvojkové reťazce).

Čo sa naučíš

1Rekurzívna funkcia

2Základný prípad

3Priebeh rekurzie

3.1Výpis pred volaním a po ňom

3.2Sledovanie hĺbky

4Rekurzívne algoritmy

4.1Súčet cifier

4.2Mocnina

4.3Najväčší spoločný deliteľ

4.4Palindróm

4.5Fibonacciho čísla a cena opakovaných výpočtov

4.6Hanojské veže

4.7Všetky možnosti: dvojkové reťazce

4.8Súčet čísel vo vnorenom zozname

5Rekurzia alebo cyklus?

6Časté chyby

Zhrnutie

Úlohy na precvičenie

Done reading?