##### IB111 skupina 10 #####
##### cvičení 11


### REKURZE

__ÚKOL 1__
Napište rekurzivní funkci, která počítá n-tý prvek posloupnosti definované
následujícím induktivním způsobem:

a(0) = 5
a(n) = 2 ⋅ a(n-1) − 1

>>> print(sequence(0))
5
>>> print(sequence(2))
17
>>> print(sequence(3))
33


__ÚKOL 2__
Napište funkci check_string(), která zkontroluje, zda daný vstupní text je ve
tvaru 'a'*n + 'b'*n (zapsano v pythonové syntaxi) pro přirozená n. Funkce bude
vstupní text kontrolovat rekurzivně. Doporučuji použít metodu 'zmenši a panuj',
tzn. nejprve rozmyslet, jak lze původní problém kontroly textu zmenšit na
jednodušší a jak by mohla vypadat nejjednodušší instance tohoto problému.
Funkce vrací True nebo False

>>> check_string('aaaabbbb')
True
>>> check_string('aaabb')
False
>>> check_string('abab')
False
>>> check_string('bbaa')
False


__ÚKOL 3__
Napište funkci koch(n), která pomocí želví grafiky vykreslí kochovu křivku
s hloukou zanoření n. Příklady výstupu pro různá n jsou v souboru koch.jpg.


__ÚKOL 4__
Napište funkci binary_search(value, numbers), která zjistí, zda se hodnota value
nachází ve vzestupně uspořádaném seznamu numbers. Funkce musí mít logaritmickou
časovou složitost. Pozor na to, že kopírování seznamu má lineární časovou složitost
vzhledem k počtu prvků. Je tedy vhodné napsat si pomocnou funkci, která bude hledat
zadané číslo v části seznamu ohraničeném 2 parametry (např. left a right pro levou 
a pravou mez intervalu, ve kterém hledáme).

>>> print(binary_search(5, [1, 2, 5, 8]))
True
>>> print(binary_search(4, [1, 2, 5, 8]))
False



__ÚKOL 5__
Metodu rozděl a panuj lze využít k efektivním algoritmům pro řazení. Jeden z možných
přístupů je vybrat libovolný prvek (tzv. pivot), a všechna ostatní čísla rozdělit na
2 části – menší než pivot a větší než pivot. Tyto dvě části seřadíme rekurzivně
a spojíme do výsledného pole. Implementujte
rozdělování prvků na místě (bez potřeby vytváření nových seznamů).
Můžete si přečíst podrobnosti o QuickSortu na Khan Academy
https://www.khanacademy.org/computing/computer-science/algorithms#quick-sort

>>> print(quicksort([3, 2, 4, 8, 9, 7, 6, 1, 5]))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

