====== 7. Rekurze ======

V řešení k příkladům z cvičení v třetím týdnu byla jedna z možností, jak stanovit největší společný dělitel, pomocí funkce, která ve svém těle volala samu sebe:

<code python>
# Uloha 7 z cv03 pomoci rekurze

def gcd(m,n):
    if n == 0:   # pri rekurzivnim volani je nutne mit ve funkci podminku, ktera ukonci funkci
        return m
    else:  # pokud ukoncovaci podminka neni splnena, funkce zavola samu sebe s upravenymi argumenty
        return gcd(n, m%n)  # funkce vola samu sebe
</code>

<code python>
# Uloha 7 z cv03 pomoci cyklu
def gcd(m,n):
    while n != 0:
        m, n = n, m%n 
    return m
</code>

Formálně tedy při rekurznivním volání je ve funkci s jedním nebo více argumenty podmínka na základě které se buď zavolá funkce znovu s novým argumentem, nebo se funkce ukončí

<code python>
def funkce(argument):
   if podminka:
      funkce(novy_argument)      
</code>


<code python>
# vypis cisel od 0 do 9 pomoci rekurze

def vypisuj(i,N):
    if i<N:  # pokud je i mensi nez N, vypise i0 a zavola funkci pro i+1
        print(i,end = ' ')
        vypisuj(i+1,N)
    
    
vypisuj(0,10)
</code>


pro pochopení, jak program prochází funkci při rekurzivním volání, a jak následně funkce opouští, si přidáme ještě jeden výpis a využijem debuger (snížíme počet čísel na 3)


<code python>
# vypis cisel od 0 do 3 pomoci rekurze

def vypisuj(i,N):
    if i<N:  # pokud je i mensi nez N, vypise i0 a zavola funkci pro i+1
        print(i,end = ' ')
        vypisuj(i+1,N)
        print(i,end = ' ')  # vypis i po vystupu z funkce (v momente, kdy neni splne podminka)

vypisuj(0,3)
</code>


Úloha 1 - Nalezení maximálního čísla v seznamu

  * Vezmeme první prvek v seznamu a dále zavoláme funkci pro nalezení maximalního prvku ve zbylém seznamu
  * Poté porovnáme obě hodnoty a vrátíme větší hodnotu
  * Pokud je délka seznamu == 1, vrátíme prvek tohoto seznamu


<code python>
def najdi_maximum(seznam):

    # <vas kod>    
    
</code>


Úloha 2 - Pomocí rekurze implementujte funkci, která vrátí n-tý člen (indexujeme od 0) [[https://cs.wikipedia.org/wiki/Fibonacciho_posloupnost|Fibonacciho posloupnosti]] - pokuste se poté o efektivnější implementaci, která bude využívat již vypočítané hodnoty posloupnosti, které budou ukládány v globálně dostupné proměnédostupném poli - zamyslete se nad implementací jak pomocí slovníku tak pomocí pole


<code python>
# Fib. posloupnost pomoci rekurze

def myfibonacci(n):
    
    # <vas kod>

n = 10
Fn =  myfibonacci(n)
print("F({0:d}) = {1:d}".format(n,Fn))

</code>


Úloha 3 - Pomocí rekurze napište funkci, která ze seznamu tvořeného seznamy, vrátí 1D seznam

Vstup:

<code python>
[1, 2, [3, 4, [5, 7], 3], 4]
</code>

Výstup

<code python>
[1, 2, 3, 4, 5, 7, 3, 4]
</code>


<code python>
vstup = [[1, 2, [3, 4, [5, 7], 3], 4]]

def narovnej(vstup):
    # <vas kod>
</code>


Úloha 4 - Pomocí rekurze najděte cestu na konec "bludiště".

  * Pro jednoduchost budeme předpokládat 1D bludiště, kde index pole bude značit jednotlivá políčka od 0 do 5, kdy 0 představuje zeď a 5 je cíl. Start bude na políčku 2.
  * V programu bude funkce, která zjistí, jestli se nenacházíte v cíli (konec hledání), funkce vrátí True
  * Nebo ve zdi nebo na políčku, přes které jste již šli, funkce vrátí False
  * Nebo zavolá samu sebe s argumentem x-1 nebo x+1 (posun na sousední poličko)
  * V každém kroku ukládejte hodnoty ''%%True%%'' do pole, značícího již navštívená políčka
  * Pokud je návratová hodnota funkce ''%%True%%'', uložte do pole ukazujícího správnou cestu hodnotu ''%%True%%''


<code python>

</code>


===== Úlohy ve zbytku cvičení nebo na doma =====


Úloha 5 - Implementujte Euklideův algoritmus pro výpočet největšího společného dělitele pomocí rekurzivního násobení matice

Při Euklidově algoritmu (úloha v třetím cvičení) dochází k opakovanému odečítání menší z dvojice čísel od většího čísla, až dokud jsou si obě čísla rovny

Opakované odečítání dvojice čísel lze zapsat jako rekurzivní součin matic. Pro dvojici čísel ''%%m%%'' a ''%%n%%'', kde ''%%m > 1%%'': $$\begin{bmatrix} m_{k+1} \cr n_{k+1} \end{bmatrix} =  \begin{bmatrix} 1 & -1 \cr 0 & 1 \end{bmatrix} \begin{bmatrix} m_{k} \cr n_{k} \end{bmatrix}$$ Pokud je ''%%m < n%%'', pak dojde k prohození jejich hodnot a vypočet pokračuje až do ''%%m == n%%''


<code python>

</code>


Úloha 6 - Efektivnější varianta Euklideova algoritmu pro výpočet největšího společného dělitele pomocí maticového násobení

Opakované odečítání dvojice čísel lze zapsat jako rekurzivní součin matic. Pro dvojici čísel ''%%m%%'' a ''%%n%%'', kde ''%%m > 1%%'': $$\begin{bmatrix} m_{k+1} \cr n_{k+1} \end{bmatrix} =  \begin{bmatrix} 0 & 1 \cr 1 & -(\frac{m}{n}) \end{bmatrix} \begin{bmatrix} m_{k} \cr n_{k} \end{bmatrix}$$ Pokud je ''%%m < n%%'', pak dojde k prohození jejich hodnot a vypočet pokračuje až do ''%%m == n%%''. ($\frac{m}{n}$) je zaokrouhlen dolu


<code python>

</code>