Rekurze
IB111 Úvod do programování skrze Python
2015
1 / 64
XKCD: Tabletop Roleplaying
https://xkcd.com/244/
2 / 64
To iterate is human, to recurse divine. (L. Peter Deutsch)
3 / 64
Rekurze
použití funkce při její vlastní definici
volání sebe sama (s jinými parametry)
4 / 64
Sebereference
https://xkcd.com/688/
5 / 64
Sebereferenční test
1 Které písmeno není správnou odpovědí na žádnou otázku:
(A) A (B) C (C) B
2 Odpověď na 3. otázku je:
(A) stejná jako na 1. otázku (B) stejná jako na 2.
otázku (C) jiná než odpovědi na 1. a 2. otázku
3 První otázka, na kterou je odpověď A, je otázka:
(A) 1 (B) 2 (C) 3
Hlavolamikon
6 / 64
Piráti
5 pirátů si dělí poklad: 100 mincí
nejstarší pirát navrhne rozdělení, následuje hlasování
alespoň polovina hlasů ⇒ rozděleno, hotovo
jinak ⇒ navrhující pirát zabit, pokračuje druhý nejstarší
(a tak dále) (rekurze!)
priority
1 přežít
2 mít co nejvíce mincí
3 zabít co nejvíc ostatních pirátů
složitější varianty: 6 pirátů a 1 mince, 300 pirátů a 100 mincí
7 / 64
Rekurze a sebereference
Rekurze a sebereference – klíčové myšlenky v informatice
některé souvislosti:
matematická indukce
funkcionální programování
rekurzivní datové struktury
gramatiky
logika, neúplnost
nerozhodnutelnost, diagonalizace
8 / 64
Rekurze a sebereference
... nejen v informatice
M. C. Escher; Drawing Hands, 1948
Gödel, Escher, Bach: An Eternal Golden Braid; Douglas
Hofstadter
9 / 64
Rekurze a úvodní programování
uvedené aplikace rekurze a sebereference často poměrně
náročné
hodí se pořádně pochopit rekurzi na úrovni
jednoduchých programů
10 / 64
Faktoriál
n! = 1 · 2 · · · (n − 1) · n
f (n) =
1 pokud n = 1
n · f (n − 1) pokud n > 1
11 / 64
Faktoriál iterativně (pomocí cyklu)
def fact(n):
f = 1
for i in range(1,n+1):
f = f * i
return f
12 / 64
Faktoriál rekurzivně
def fact(n):
if n == 1: return 1
else: return n * fact(n-1)
13 / 64
Faktoriál rekurzivně – ilustrace výpočtu
fact(4)
4 * fact(3)
3 * fact(2)
2 * fact(1)
1
1
2
6
24
14 / 64
Příklad: výpis čísel
Vymyslete funkci, která:
vypíše čísla od 1 do N
pomocí rekurze – bez použití cyklů for, while
15 / 64
Příklad: výpis čísel
Vymyslete funkci, která:
vypíše čísla od 1 do N
pomocí rekurze – bez použití cyklů for, while
def vypis(n):
if n > 1:
vypis(n-1)
print n
16 / 64
Co udělá tento program?
def test(n):
print n
if n > 1:
test(n-1)
print -n
test(5)
17 / 64
Ilustrace zanořování
test(1)
test(2)
test(3)
3
2
1 -1
-2
-3
18 / 64
Nepřímá rekurze
def suda(n):
print "suda", n
licha(n-1)
def licha(n):
print "licha", n
if n > 1:
suda(n-1)
suda(10)
19 / 64
Rekurzivní stromeček
20 / 64
Rekurzivní stromeček
nakreslit stromeček znamená:
udělat stonek
nakreslit dva menší stromečky (pootočené)
21 / 64
Stromeček želví grafikou
def stromecek(delka):
forward(delka)
if delka > 10:
left(45)
stromecek(0.6 * delka)
right(90)
stromecek(0.6 * delka)
left(45)
back(delka)
22 / 64
Podoby rekurze, odstranění rekurze
koncová rekurze (tail recursion)
rekurzivní volání je poslední příkaz funkce
např. uvedená funkce pro faktoriál
lze vesměs přímočaře nahradit cyklem
„plná rekurze
„zanořující se volání
např. stromeček
lze přepsat bez použití rekurze za použití zásobníku
rekurzivní podoba často výrazně elegantnější
23 / 64
Hanojské věže aneb O konci světa
video:
http://www.fi.muni.cz/~xpelanek/IB111/
hanojske_veze/
klášter kdesi vysoko v horách u města Hanoj
velká místnost se třemi vyznačenými místy
64 různě velkých zlatých disků
podle věštby mají mniši přesouvat disky z prvního na třetí
místo
a až to dokončí ...
24 / 64
Hanojské věže: pravidla
N disků různých velikostí naskládaných na sobě
vždy může být jen menší disk položen na větším
možnost přesunout jeden horní disk na jiný kolíček
cíl: přesunout vše z prvního na třetí
25 / 64
Hanojské věže: řešení
A B C A B C A B C A B C
A B CA B CA B CA B C
26 / 64
Hanojské věže: výstup programu
>>> presun(3, "A", "B", "C")
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
27 / 64
Hanojské věže: rekurzivní řešení
def presun(n, odkud, kam, kudy):
if n == 1:
print odkud, "->", kam
else:
presun(n-1, odkud, kudy, kam)
presun(1, odkud, kam, kudy)
presun(n-1, kudy, kam, odkud)
28 / 64
Řešení včetně vypisování stavu
*
***
*****
-------------------
***
***** *
-------------------
***** *** *
-------------------
*
***** ***
-------------------
*
*** *****
-------------------
* *** *****
-------------------
29 / 64
Stav úlohy, reprezentace
stav úlohy = rozmístění disků na kolících
disky na kolíku A → seznam
celkový stav:
3 proměnné, v každé seznam – nepěkné
seznam seznamů, kolíky interně značíme 0, 1, 2
příklad stavu (6 disků): [[4], [5, 2, 1], [6, 3]]
30 / 64
Řešení včetně vypisování stavu
def hanoi(n, odkud, kam, kudy, stav):
if n==1:
disk = stav[odkud].pop()
stav[kam].append(disk)
vypis_stav(stav)
else:
hanoi(n-1, odkud, kudy, kam, stav)
hanoi(1, odkud, kam, kudy, stav)
hanoi(n-1, kudy, kam, odkud, stav)
def res_hanoi(n):
stav = [ range(n,0,-1), [], [] ]
vypis_stav(stav)
hanoi(n, 0, 2, 1, stav)
31 / 64
Vypisování stavu – jednoduše
def vypis_stav(stav):
print stav
print "--"
def vypis_stav(stav):
for i in range(3):
print "Kolik", chr(ord(’A’)+i), stav[i]
print "--"
32 / 64
Vypisování stavu – textová grafika
def vypis_stav(stav):
n = sum([ len(s) for s in stav ])
for y in range(n+1):
radek = ""
for kolik in range(3):
for x in range(-n+1, n):
if len(stav[kolik]) > n-y and\
abs(x) < stav[kolik][n-y]:
radek += "*"
else:
radek += " "
radek += " "
print radek
print "-"*(n*6+1)
33 / 64
Sierpi´nského fraktál
rekurzivně definovaný geometrický útvar
34 / 64
Sierpi´nského fraktál
35 / 64
Sierpi´nského fraktál: kód
def sierpinski(n, delka):
if n == 1:
trojuhelnik(delka)
else:
for i in range(3):
sierpinski(n - 1, delka)
forward((2 ** (n - 1)) * delka)
right(120)
36 / 64
Další podobné fraktály
37 / 64
Robotanik
tutor.fi.muni.cz, úloha Robotanik
jednoduché „grafické programování robota
těžší příklady založeny na rekurzi
vizualizace průběhu „výpočtu , zanořování a vynořování z
rekurze
38 / 64
Robotanik – Kurz počítání
rekurze jako „paměť
39 / 64
Robotanik
40 / 64
Pokrývání plochy L kostičkami
mřížka 8 × 8 s chybějícím levým horním polem
úkol: pokrýt zbývající políčka pomocí L kostiček
rozšíření:
rozměr 2n × 2n
chybějící libovolné pole
obarvení 3 barvami, aby sousedi byli různí
41 / 64
Ukázky řešení
42 / 64
Řešení
rozdělit na čtvrtiny
umístit jednu kostku
rekurzivně aplikovat řešení na jednotlivé části
43 / 64
Příklady použití rekurze v informatice
Euclidův algoritmus – NSD
vyhledávání opakovaným půlením
řadicí algoritmy (quicksort, mergesort)
generování permutací, kombinací
fraktály
prohledávání grafu do hloubky
gramatiky
44 / 64
Euklidův algoritmus rekurzivně
def nsd(a,b):
if b == 0:
return a
else:
return nsd(b, a % b)
45 / 64
Vyhledávání opakovaným půlením
hra na 20 otázek
hledání v seznamu
hledání v binárním stromu
46 / 64
Vyhledávání: rekurzivní varianta
def binarni_vyhledavani(hodnota, seznam,
spodni_mez, horni_mez):
if spodni_mez > horni_mez:
return False
stred = (spodni_mez + horni_mez)/2
if seznam[stred] < hodnota:
return binarni_vyhledavani(hodnota, seznam,
stred+1, horni_mez)
elif seznam[stred] > hodnota:
return binarni_vyhledavani(hodnota, seznam,
podni_mez, stred-1)
else:
return True
47 / 64
Řadicí algoritmy
quicksort
vyber pivota
rozděl na menší a větší
zavolej quicksort na podčásti
mergesort
rozděl na polovinu
každou polovinu seřaď pomocí mergesort
spoj obě poloviny
48 / 64
Generování permutací, kombinací
permutace množiny = všechna možná pořadí
příklad: permutace množiny {1, 2, 3, 4}
jak je vypsat systematicky?
jak využít rekurzi?
k-prvkové kombinace n-prvkové množiny = všechny
možné výběry k prvků
příklad: 3-prvkové kombinace množiny {A, B, C, D, E}
jak je vypsat systematicky?
jak využít rekurzi?
49 / 64
Kombinace
n
k
=
n − 1
k − 1
+
n − 1
k
def kombinace(seznam, k):
if k == 0: return [ [] ]
if len(seznam) < k: return []
vystup = [ ]
for komb in kombinace(seznam[1:], k-1):
komb.append(seznam[0])
vystup.append(komb)
vystup.extend(kombinace(seznam[1:], k))
return vystup
50 / 64
Nevhodné použití rekurze
ne každé použití rekurze je efektivní
Fibonacciho posloupnost (králíci):
f1 = 1
f2 = 1
fn = fn−1 + fn−2
1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
Vi Hart: Doodling in Math: Spirals, Fibonacci, and Being a Plant
51 / 64
Fibonacciho posloupnost: rekurzivně
def fib(n):
if n <= 2: return 1
else: return fib(n-1) + fib(n-2)
52 / 64
Fibonacciho posloupnost: rekurzivní výpočet
fib(4)
fib(2)
1
fib(3)
fib(2)fib(1)
1 1
fib(5)
+
+ + fib(3)
fib(2)fib(1)
1 1
+
53 / 64
Problém N dam
šachovnice N × N
rozestavit N dam tak, aby se vzájemně neohrožovaly
zkuste pro N = 4
pozn. speciální případ „problému splnění podmínek
54 / 64
Problém N dam – řešení
55 / 64
Problém N dam – algoritmus
ilustrace algoritmu backtracking
hrubá síla, ale „chytře
začneme s prázdným plánem, systematicky zkoušíme
umisťovat dámy
pokud najdeme kolizi, vracíme se a zkoušíme jinou
možnost
přirozený rekurzivní zápis
56 / 64
Problém N dam – backtracking
řešení
57 / 64
Problém N dam – reprezentace stavu
pro každé pole si pamatujeme, zda na něm je/není dáma
dvourozměrný seznam True/False
pro každou dámu si pamatujeme její souřadnice
seznam dvojic xi , yi
pro každý řádek si pamatujeme, v kterém sloupci je dáma
seznam čísel (xi )
nejvýhodnější reprezentace
58 / 64
Problém N dam – řešení
def vyres_damy(n, stav):
if len(stav) == n:
vypis(stav)
return True
else:
for i in range(n):
stav.append(i)
if zkontroluj(stav):
if vyres_damy(n, stav): return True
stav.pop()
return False
59 / 64
Kdy se ohrožují dvě dámy?
x
y
1
1
x2
y2
60 / 64
Kdy se ohrožují dvě dámy?
x
y
1
1
x2
y2
x1 = x2
y1 = y2
x1 + y1 = x2 + y2
x1 − y1 = x2 − y2
61 / 64
Problém N dam – řešení
def vypis(stav):
for y in range(len(stav)):
for x in range(len(stav)):
if stav[y]==x: print "X",
else: print ".",
print
print
def zkontroluj(stav):
for y1 in range(len(stav)):
x1 = stav[y1]
for y2 in range(y1+1, len(stav)):
x2 = stav[y2]
if x1 == x2 or x1-y1 == x2-y2 or x1+y1 == x
return False
return True 62 / 64
Backtracking – další příklady použití
mnoho logických úloh:
Sudoku a podobné úlohy
algebrogramy (SEND + MORE = MONEY)
optimalizační problémy (např. rozvrhování, plánování)
obecný „problém splnění podmínek
63 / 64
Shrnutí
rekurze: využití rekurze pro definici sebe sama
logické úlohy: Hanojské věže, L kostičky, dámy na
šachovnici
fraktály
aplikace v programování: vyhledávání, řazení,
prohledávání grafu
klíčová myšlenka v informatice
nezapomeňte na piráty
64 / 64