Rekurze IB111 Úvod do programování skrze Python 2013 1 / 55 To iterate is human, to recurse divine. (L. Peter Deutsch) 2 / 55 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) priority 1 přežít 2 mít co nejvíce mincí 3 zabít co nejvíc ostatních pirátů (6 pirátů a 1 mince, 300 pirátů a 100 mincí) 3 / 55 Rekurze použití funkce při její vlastní definici volání sebe sama (s jinými parametry) 4 / 55 Rekurze a sebe-reference Rekurze a sebe-reference – klíčové myšlenky v informatice některé souvislosti: matematická indukce funkcionální programování rekurzivní datové struktury gramatiky logika, neúplnost nerozhodnutelnost, diagonalizace 5 / 55 Rekurze a úvodní programování uvedené aplikace rekurze a sebe-reference často poměrně náročné hodí se pořádně pochopit rekurzi na úrovni jednoduchých programů 6 / 55 Faktoriál n! = 1 · 2 · · · (n − 1) · n f (n) = 1 pokud n = 1 n · f (n − 1) pokud n > 1 7 / 55 Faktoriál iterativně (pomocí cyklu) def fact(n): f = 1 for i in range(1,n+1): f = f * i return f 8 / 55 Faktoriál rekurzivně def fact(n): if n == 1: return 1 else: return n * fact(n-1) 9 / 55 Faktoriál rekurzivně – ilustrace výpočtu fact(4) 4 * fact(3) 3 * fact(2) 2 * fact(1) 1 1 2 6 24 10 / 55 Příklad: výpis čísel Vymyslete funkci, která: vypíše čísla od 1 do N pomocí rekurze – bez použití cyklů for, while 11 / 55 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 12 / 55 Co udělá tento program? def test(n): print n if n > 1: test(n-1) print -n test(5) 13 / 55 Ilustrace zanořování test(1) test(2) test(3) 3 2 1 -1 -2 -3 14 / 55 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) 15 / 55 Rekurzivní stromeček 16 / 55 Rekurzivní stromeček nakreslit stromeček znamená: udělat stonek nakreslit dva menší stromečky (pootočené) 17 / 55 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) 18 / 55 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ší 19 / 55 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čí ... 20 / 55 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í 21 / 55 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 22 / 55 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 23 / 55 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) 24 / 55 Sierpi´nského fraktál rekurzivně definovaný geometrický útvar 25 / 55 Sierpi´nského fraktál 26 / 55 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) 27 / 55 Další podobné fraktály 28 / 55 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 29 / 55 Robotanik – Kurz počítání rekurze jako „paměť 30 / 55 Robotanik 31 / 55 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í 32 / 55 Ukázky řešení 33 / 55 Řešení rozdělit na čtvrtiny umístit jednu kostku rekurzivně aplikovat řešení na jednotlivé části 34 / 55 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 35 / 55 Euklidův algoritmus rekurzivně def nsd(a,b): if b == 0: return a else: return nsd(b, a % b) 36 / 55 Vyhledávání opakovaným půlením hra na 20 otázek hledání v seznamu hledání v binárním stromu 37 / 55 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 38 / 55 Ř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 39 / 55 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? 40 / 55 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 41 / 55 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 42 / 55 Fibonacciho posloupnost: rekurzivně def fib(n): if n <= 2: return 1 else: return fib(n-1) + fib(n-2) 43 / 55 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 + 44 / 55 Problém N dam šachovnice N × N rozestavit N dam tak, aby se vzájemně neohrožovaly zkuste pro N = 4 45 / 55 Problém N dam – řešení 46 / 55 Problém N dam – algoritmus ilustrace algoritmu backtracking speciální případ obecného typu problémů („problém splnění podmínek ) a algoritmu 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 47 / 55 Problém N dam – backtracking řešení 48 / 55 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 49 / 55 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 50 / 55 Kdy se ohrožují dvě dámy? x y 1 1 x2 y2 51 / 55 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 52 / 55 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 53 / 55 Backtracking – další příklady použití mnoho logických úloh: Sudoku a podobné úlohy algebrogramy (SEND + MORE = MONEY) optimalizační problémy obecný „problém splnění podmínek 54 / 55 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 55 / 55