10. Rekurze¶

10.1.1. Součet čísel¶

Napište rekurzivní funkci, která zjistí součet přirozených čísel od 1 do n. Při vymýšlení funkce series_sum(n) si představte, že máte k dispozici funkci series_sum(k) pro libovolné k < n. Nezapomeňte na bázový případ.

def series_sum(n: int) -> int:
    pass

def test_series_sum() -> None:
    assert series_sum(1) == 1
    assert series_sum(5) == 15
    assert series_sum(10) == 55
    assert series_sum(100) == 5050

10.1.2. Prvek posloupnosti¶

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 \cdot a_{n - 1} - 1\)

def sequence(n: int) -> int:
    pass

assert sequence(0) == 5
assert sequence(1) == 9
assert sequence(2) == 17
assert sequence(3) == 33

10.1.3. Zašroubování žárovky¶

Napište rekurzivní funkci, která n-krát vypíše „twist“.

def screwing(n: int) -> None:
    pass

screwing(3)
# Ocekavany vystup:
# twist
# twist
# twist

10.1.4. Součet seznamu čísel¶

Napište rekurzivní funkci pro součet seznamu čísel.

def list_sum(numbers: List[int]) -> int:
    pass

def test_list_sum() -> None:
    assert list_sum([1, 8, 2, 0, 4, 2]) == 17

10.1.5. Binární vyhledávání¶

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).

def binary_search(value: int, numbers: List[int]) -> bool:
    pass

def test_binary_search() -> None:
    assert binary_search(5, [1, 2, 5, 8]) == True
    assert binary_search(4, [1, 2, 5, 8]) == False

10.2.1. Hanojské věže¶

Máme 3 věže, na jedné z nich (budeme jí říkat zdrojová), je nasunuto n kotoučů různé velikosti od největšího po nejmenší. Úkolem je přesunout všechny kotouče ze zdrojové na cílovou věž, přičemž vždy můžeme přesouvat pouze jeden kotouč a nikdy nesmíme dát větší kotouč na menší. Pokud jste se s hrou ještě nesetkali, vyzkoušejte si ji. Naším úkolem teď bude vymyslet rekurzivní algoritmus, který přesune n kotoučů ze zdrojové na cílovou věž, resp. vypíše kroky, které je potřeba k přesunu udělat. Řešení pro 3 kotouče, a věže pojmenované ‘A’ (zdrojová věž), ‘C’ (cílová věž) a ‘B’ (pomocná věž):

>>> hanoi(3, 'A', 'C', 'B')

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

# Vypise premistovani kotoucu pri reseni Hanojskych vezi.
# - n:         pocet kotoucu
# - source:    tyc, na ktere jsou kotouce na zacatku
# - target:    tyc, na kterou chceme kotouce premistit
# - auxiliary: pomocna tyc, kterou lze vyuzit v prubehu premistovani
def hanoi(n: int, source: str, target: str, auxiliary: str) -> None:
    pass

hanoi(3, 'A', 'C', 'B')

10.2.2. Hanojské věže graficky¶

Rozšiřte předchozí úlohu o vykreslování mezistavů po každém přesunu pomocí ascii grafiky.

>>> hanoi(3, 'A', 'C', 'B')

    #      |      |
   ###     |      |
  #####    |      |
  -----  -----  -----
    A      B      C

    |      |      |
   ###     |      |
  #####    |      #
  -----  -----  -----
    A      B      C

...

10.2.3. Maximum a minimum¶

S využitím techniky rozděl a panuj napište funkci pro zjištění minima a maxima ze seznamu čísel. Vaše funkce by měla obsahovat 2 rekurzivní volání. Zkuste se vyhnout kopírování části seznamu (podobně jako v úloze Binární vyhledávání).

def min_max(numbers: List[int]) -> Tuple[int, int]:
    pass

def test_min_max() -> None:
    assert min_max([8, 4, 3, 5, 9, 2, 1, 7, 6]) == (1, 9)

10.2.4. Rychlé řazení¶

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. Rozdělení čísel na prvky menší a větší než pivot je jednoduché, pokud povolíme vytvářet nové seznamy (tím se mírně zhoršuje paměťová složitost). Implementujte tento rekurzivní algoritmus, nezapomeňte na bázový případ. Můžete si přečíst podrobnosti o QuickSortu na Khan Academy a pokusit se implementovat rozdělování prvků na místě (bez potřeby vytváření nových seznamů).

# vraci serazene pole 'array' (samotne pole 'array' nemeni)
def quick_sort(array: List[int]) -> List[int]:
    pass

def test_quick_sort() -> None:
    assert quick_sort([2, 7, 8, 1, 4, 5, 9, 3, 6]) == list(range(1, 10))

10.3.1. Vnořené čtverce¶

Úkolem je napsat rekurzivní funkci, která vykreslí vnořené čtverce. Parametr funkce bude udávat, kolik čtverců má být vykresleno. Při vymýšlení rekurzivní funkce si nejprve ujasněte (můžete zapsat do komentáře), co funkce dělá – není důležité jen to, co želva vykreslí, ale také to, kde skončí a jakým směrem bude natočená. Dále si představte, že již máte k dispozici funkci, která umí kreslit menší počty čtverců a využijte ji k napsání těla funkce. Nezapomeňte na bázový případ. Funkce bude obsahovat jediné rekurzivní volání, takže by bylo jednoduché ji přepsat pomocí cyklu bez rekurze (můžete si vyzkoušet).

from turtle import Turtle
julie = Turtle()
julie.speed(10)

# depth: kolik ctvercu vykreslit
# length: delka strany nejvetsiho ctverce
def nested_squares(depth: int, length: float = 180.0) -> None:
    pass

nested_squares(8)

10.3.2. Strom¶

S využitím techniky rozděl a panuj napište rekurzivní funkci pro vykreslení stromku, jako vidíte na obrázku. Po vykreslení základního stromku můžete vyzkoušet různé variace, např. změnit stupeň větvení, délku větví, naklonění větví atd.

from turtle import Turtle
julie = Turtle()
julie.speed(10)
julie.left(90)

# length: delka kmenove cary
def tree(length: float) -> None:
    pass

tree(90)

10.3.3. Kochova vločka¶

Napište rekurzivní funkci pro vykreslení Kochovy křivky. Vhodným složením tří Kochových křivek (jakoby do trojúhelníka) získáte Kochovu vločku.

from turtle import Turtle
julie = Turtle()
julie.speed(10)
julie.setposition(-190, 0)

# depth: pocet rekurzivnich zanoreni
# size: sirka krivky
def koch(depth: int = 5, size: float = 380.0) -> None:
    pass

koch(5)

10.3.4. Sierpinského trojúhelník¶

Napište rekurzivní funkci pro vykreslení Sierpinského trojúhelníka (není nutné „nezpracované“ trojúhelníky vyplňovat černou barvou).

from turtle import Turtle
julie = Turtle()
julie.speed(10)

# depth: pozadovana hloubka rekurzivniho zanoreni
# length: delka strany trojuhelnika
def sierpinski_triangle(depth: int, length: float = 180.0) -> None:
    pass

sierpinski_triangle(5)

10.4.1. Tetranacciho posloupnost¶

Napište efektivní rekurzivní funkci pro výpočet n-tého čísla Tetranacciho posloupnosti, která je definovaná následujícím induktivním způsobem:

\(a_0 = 0\), \(a_1 = 1\), \(a_2 = 1\), \(a_3 = 2\),

\(a_n = a_{n - 1} + a_{n - 2} + a_{n - 3} + a_{n - 4}\)