Rekurze co je to rekurze? - víme, že v pythonu může funkce volat jinou funkci - volá-li funkce sama sebe, nazývá se rekurzivní funkcí - rekurzivní funkce potřebuje podmínku pro své ukončení, jinak pojede v nekonečném cyklu - nejčastěji se ukončení funkce definuje pomocí if podmínky co je to rekurze? - počet iterací - nejčastěji má python nastavený limit pro počet rekurzívních operací nastavený na 1000 - v jupyteru to bývá nastaveno na 3000 rekurze v praxi Napišme si funkci, která odpočítá od daného čísla n do 0. - takováto funkce bude odpočítávat od 5 až do svého limitu RecursionError: rekurze v praxi (2) - je dobrou praxí používat if větev na případ bez rekurze a else větev funkce pro rekurzi Cvičení 1. Napište rekurzivní funkci s if podmínkou, která vypíše všechny sudé čísla od n do 0, kde n je argument funkce. nápověda: modulo operátor se v pythonu značí % - modulo ukáže zbytek po celočíselném dělení rekurze v praxi (3) - s každým rekurzivním voláním funkce vznikají nový prostor s lokálními proměnnými a na které vidí jen ona sama, čili: suma(3) #první zavolání funkce 3 + suma(2) #druhé zavolání funkce 3 + 2 + suma(1) #třetí zavolání funkce 3 + 2 + 1 + suma(0) #čtvrté zavolání funkce 0 #vrácení hodnoty ze čtvrtého zavolání funkce (suma(0) vrátí 0) 1 + 0 #vrácení hodnoty z třetího zavolání funkce (suma(1) vrátí 1) 2 + 1 #vrácení hodnoty z druhého zavolání funkce (suma(2) vrátí 3) 3 + 3 #vrácení hodnoty z prvního zavolání funkce (suma (3) vrátí 6) Cvičení 2. Napište rekurzivní funkci s if podmínkou, která počítá faktoriál čísla n, kde n je argument funkce. nápověda: faktoriál 3! = 3*2*1 = 6 svoji funkci provnejte s: Cvičení 3. Napište rekurzivní funkci s if podmínkou, která vypíše n-té číslo Fibonacciho posloupnosti, kde n je argumentem funkce. nápověda: rychlost rekurzivní funkce = bývají pomalé pro zjištění rychlosti funkce můžeme použít: dva type rekurze - 1. Přímá (ang. Direct) - typ rekuze, který volá sám sebe (s tímhle typem jsem pracovali doteď) dva type rekurze - 1. Nepřímá (ang. Indirect) - typ rekuze, který volá jinou funkci, která volá funkci původní Cvičení 4. Napište rekurzivní funkci s if podmínkou, která vypíše největšího společného dělitele (NSD) dvou čísel. nápověda: a. použijte operátor modulo % b. použijte Eukleidův algoritmus i. pokud je a=0 pak NSD(0,b)=b, pokud je b=0 pak NSD(a,0)=a ii. spočítejte zbytek po celočíselném dělení = c iii. využijte platnosti NSD(a,b)=NSD(b,c) Cvičení 5. Napište rekurzivní funkci se dvěma argumenty, která ověří jestli první z argumentů je mocninou druhého argumentu. nápověda (1): nápověda (2): použijte operátor modulo % použijte podmínku if dvakrát Cvičení 6. Napište rekurzivní funkci se dvěma argumenty, která spočítá nejmenší společný násobek (NSN). nápověda: - NSN dvou čísel je nejmenší kladné celé číslo, které lze vydělit každým z nich - NSN(12,15) = 60 Napište funkci, která spočítá NSN s využitím funkce pro největší společný dělitel NSD. nápověda: Cvičení 7. Napište rekurzivní funkci s jedním argumentem, která vypíše posloupnost Collatzeho problému. Definice: - pokud je číslo n liché, pak 3n + 1 - pokud je číslo n sudé, pak n/2 - každá takováto řada konverguje k číslu 1 (pozor z jedničky se stane 4 a ta se zase dostane na 1)