Rekurze

Rekurze je v informatice mocný nástroj, který umožňuje funkci volat samu sebe. Používá se především pro řešení problémů, které mohou být rozděleny na menší podproblémy podobného typu. Rekurze může být velmi užitečná pro řešení složitých problémů jednoduchým a elegantním způsobem.

V Pythonu je rekurze klíčovým konceptem a je často používána v různých algoritmech, jako jsou třídící algoritmy, algoritmy pro prohledávání stromů a grafů a mnoho dalších. Nicméně, než se pustíme do implementace rekurze, je důležité pochopit její základy.

Základní koncept rekurze

Rekurzivní funkce je funkce, která volá samu sebe. Každá rekurzivní funkce by měla mít:

• Základní případ: Podmínka, která zastaví rekurzi. Je to nejjednodušší forma problému, která může být vyřešena přímo bez další rekurze.
• Rekurzivní případ: Část funkce, kde se funkce volá sama se změněnými (obvykle zjednodušenými) parametry. Tento proces se opakuje, dokud se nedosáhne základního případu.

Pokud nelze základního případu dosáhnout a funkce by se volala nekonečněkrát, Python vyhodí chybu.

Ukázkový příklad: Faktoriál

Faktoriál čísla je definován jako součin všech kladných celých čísel menších nebo rovných danému číslu. Faktoriál 5 (zapsaný jako 5!) je tedy:

5! = 5 × 4 × 3 × 2 × 1 = 120

Tento problém lze snadno řešit pomocí rekurze:

def faktorial(n):
  if n == 0 # Základní případ
      return 1
  return n * faktorial(n - 1)  # Rekurzivní případ

Vysvětlení:

• Základní případ: Pokud je n 0, vrátí se 1, protože faktoriál 0! je definován jako 1.
• Rekurzivní případ: Funkce volá samu sebe s n-1 a vynásobí výsledek s n. Tento proces pokračuje, dokud není dosaženo základního případu.

Ukázkový příklad: Fibonacciho posloupnost

Fibonacciho posloupnost je posloupnost čísel, kde každé číslo je součtem dvou předchozích. Základní případy máme n == 0 a n == 1. Fibonacciho posloupnost pro představu začíná takhle:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Následující rekurzivní funkce vypočítá n-tý prvek Fibonacciho posloupnosti:

def fibonacci(n):
if n == 0:
    return 0
elif n == 1:
    return 1
return fibonacci(n-1) + fibonacci(n-2)

Výhody rekurze

• Jednoduchost kódu: Rekurzivní řešení může být mnohem jednodušší a elegantnější než iterativní.
• Rozděl a panuj: Rekurze je ideální pro problémy, které mohou být rozděleny na menší podobné problémy.

Nevýhody rekurze

• Výkon: Rekurze může být méně efektivní než iterativní řešení kvůli režijním nákladům spojeným s voláním funkcí.
• Limity zásobníku: Každá rekurzivní volání je uložena na zásobníku volání. Pokud je rekurze příliš hluboká, může způsobit chybu zásobníku.