====== 9. Rekurze ======

Při rekurzivním volání volá funkce samu sebe. Aby nedošlo k nekonečné smyčce, musí toho volání obsahovat ukončovací podmínku. Obecně lze rekurzi zapsat

<code python>
def funkce(promenna):
   if (ukoncovaci podminka):
      funkce(zmenena_promenna)         
</code>

Pomocí rekurze můžeme například implementovat **for** cyklus:

<code python>
def recursivePrint(index, array):
    if (index < len(array) ):
        print(array[index], end=' ' );
        recursivePrint(index+1, array)
        print(array[index], end=' ' );

a = []
for i in range(10):
    a.append(i*i)
    
print("List je",a)
recursivePrint(0, a);
</code>

==== Úkol 1: umocňování ====

  * Napište rekurzivní funkci ''power(x,n)'', která bude počítat $x^n$
  * Porovnejte s iterativní verzí

==== Úkol 2: narovnání ====

  * Uvažujme seznam, který může obsahovat jako prvky další seznamy, např.:
<code>
a=[1, 2, [3, [4, 5], 6, [7]], [8, 9], 10]
</code>
  * Napište funkci ''flatten'', která vytvoří jeden seznam, který bude obsahovat všechny prvky ze seznamu ''a'' vložené do tohoto seznamu.
  * Výsledkem funkce ''flatten(a)'':
<code>
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
</code>
  * K testu prvku, zda je pole (list), použijte funkci type:
<code python>
if type(x) is list:
</code>
 
==== Úkol 3: binomický koeficient ====

  * Napište funkci ''binomial(k,n)'', která počítá hodnotu $ n \choose k $
  * Můžete využít vztah $ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $
  * Počáteční podmínky $\binom{n}{0}=\binom{n}{n}=1$ a $\binom{n}{1}=\binom{n}{n-1}=n$


==== Úkol 4: výpočet Fibonacciho posloupnosti ====

Napište rekurzivní výpočet Fibonacciho posloupnosti. Pro tuto posloupnost platí:
  * $F_n = F_{n-1} + F_{n-2}$
  * První členy posloupnosti jsou $F_0 = 0$ a $F_1 = 1$.