03.19 Rekurze

Výuka

Proč Rekurze?

Rekurze je technika, kdy funkce volá sama sebe. Místo použití smyčky se problém rozloží na menší podproblémy, až se dostaneš k nejjednodušší variantě.

Proč to potřebujeme?

• Přirozené řešení - Některé problémy jsou rekurzivní povahy (stromy, fraktály, faktoriál)
• Elegantní kód - Rekurzivní řešení může být čitelnější než smyčky
• Dělení problému - Rozložíš složitý problém na menší kousky
• Procházení stromů - Nejpřirozenější způsob práce se stromovými strukturami

Představ si to jako: Ruské matrjošky. Otevřeš velkou panenku, uvnitř je menší. Otevřeš tu menší, uvnitř je ještě menší. Pokračuješ, dokud nenajdeš tu nejmenší (základní případ). Rekurze funguje stejně - řešíš problém zavoláním sebe sama s menším problémem.

Jak to funguje?

1. Funkce zavolá sama sebe s menším/jednodušším problémem
2. Každé volání má svůj vlastní "kontext" (parametry, lokální proměnné)
3. Musí existovat ZÁKLADNÍ PŘÍPAD (base case) - kdy se přestane volat
4. Rekurzivní volání postupně zmenšují problém
5. Výsledky se "staví" zpět nahoru při návratu z volání

Klíčové koncepty

• Rekurze - funkce volající sama sebe
• Základní případ (base case) - podmínka, kdy se rekurze zastaví (MUSÍ existovat!)
• Rekurzivní případ - krok, který volá funkci s menším problémem
• Volací zásobník (call stack) - každé volání se ukládá na zásobník
• Stack overflow - příliš mnoho vnořených volání vyčerpá paměť

JavaScript

Příklad 1: Nejjednodušší rekurze - power (mocnina)

function power(base, exponent) {
  if (exponent === 0) {
    return 1;  // Základní případ: cokoliv^0 = 1
  } else {
    return base * power(base, exponent - 1);  // Rekurzivní případ
  }
}

console.log(power(2, 3));
// → 8 (2 * 2 * 2)

Co se stalo?

1. power(2, 3) → 2 * power(2, 2)
2. power(2, 2) → 2 * power(2, 1)
3. power(2, 1) → 2 * power(2, 0)
4. power(2, 0) → 1 (základní případ!)
5. Vrací se zpět: 2 * 1 = 2, 2 * 2 = 4, 2 * 4 = 8

Příklad 2: Faktoriál (klasický příklad rekurze)

function factorial(n) {
  if (n === 0) {
    return 1;  // Základní případ: 0! = 1
  } else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5));
// → 120 (5 * 4 * 3 * 2 * 1)

Co se stalo?

• factorial(5) = 5 * factorial(4)
• factorial(4) = 4 * factorial(3)
• factorial(3) = 3 * factorial(2)
• factorial(2) = 2 * factorial(1)
• factorial(1) = 1 * factorial(0)
• factorial(0) = 1 (základní případ)
• Výsledek: 5 * 4 * 3 * 2 * 1 * 1 = 120

Příklad 3: Odpočet (countdown) - jednoduchý příklad

function countdown(n) {
  if (n <= 0) {
    console.log("Konec!");  // Základní případ
  } else {
    console.log(n);
    countdown(n - 1);  // Rekurzivní volání s n-1
  }
}

countdown(3);
// → 3
// → 2
// → 1
// → Konec!

Co se stalo?

• Funkce vypíše číslo a zavolá sebe s n-1
• Pokračuje, dokud n není 0 nebo menší (základní případ)
• Pak se všechna volání vrátí zpět

Příklad 4: Součet čísel v poli (rekurzivně)

function sumArray(arr) {
  if (arr.length === 0) {
    return 0;  // Základní případ: prázdné pole
  } else {
    return arr[0] + sumArray(arr.slice(1));  // První prvek + zbytek
  }
}

console.log(sumArray([1, 2, 3, 4]));
// → 10

Co se stalo?

1. sumArray([1, 2, 3, 4]) → 1 + sumArray([2, 3, 4])
2. sumArray([2, 3, 4]) → 2 + sumArray([3, 4])
3. sumArray([3, 4]) → 3 + sumArray([4])
4. sumArray([4]) → 4 + sumArray([])
5. sumArray([]) → 0 (základní případ)
6. Výsledek: 1 + 2 + 3 + 4 + 0 = 10

Příklad 5: Hledání řešení (findSolution)

function findSolution(target) {
  function find(current, history) {
    if (current === target) {
      return history;  // Našli jsme řešení!
    } else if (current > target) {
      return null;  // Přestřelili jsme
    } else {
      // Zkus obě možnosti: +5 nebo *3
      return find(current + 5, `(${history} + 5)`) ||
             find(current * 3, `(${history} * 3)`);
    }
  }
  return find(1, "1");
}

console.log(findSolution(24));
// → (((1 * 3) + 5) * 3)

Co se stalo?

• Začne s 1, zkouší buď přidat 5 nebo násobit 3
• Rekurzivně zkouší obě cesty
• Když najde řešení (current === target), vrátí historii
• Operátor || zkusí první možnost, pokud neuspěje, zkusí druhou

Příklad 6: Rekurze vs smyčka - porovnání

// Rekurzivní verze
function sumRecursive(n) {
  if (n === 0) return 0;
  return n + sumRecursive(n - 1);
}

// Iterativní verze (smyčka)
function sumIterative(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

console.log(sumRecursive(5));   // → 15
console.log(sumIterative(5));   // → 15

Co se stalo?

• Rekurzivní verze - elegantní, ale pomalejší (volací zásobník)
• Iterativní verze - rychlejší, méně paměti
• Obě dávají stejný výsledek

TypeScript

TypeScript přidává typové anotace pro rekurzivní funkce - můžeš specifikovat typ návratové hodnoty a parametrů.

Stejné příklady s typy

// Power s typy
function power(base: number, exponent: number): number {
  if (exponent === 0) {
    return 1;
  } else {
    return base * power(base, exponent - 1);
  }
}

// Faktoriál s typy
function factorial(n: number): number {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

// Countdown s void (nic nevrací)
function countdown(n: number): void {
  if (n <= 0) {
    console.log("Konec!");
  } else {
    console.log(n);
    countdown(n - 1);
  }
}

// Součet pole s generickým typem
function sumArray(arr: number[]): number {
  if (arr.length === 0) {
    return 0;
  } else {
    return arr[0] + sumArray(arr.slice(1));
  }
}

// findSolution s typovanou vnitřní funkcí
function findSolution(target: number): string | null {
  function find(current: number, history: string): string | null {
    if (current === target) {
      return history;
    } else if (current > target) {
      return null;
    } else {
      return find(current + 5, `(${history} + 5)`) ||
             find(current * 3, `(${history} * 3)`);
    }
  }
  return find(1, "1");
}

TypeScript přidává:

• ✅ Typovou kontrolu - TS zkontroluje, že vracíš správný typ
• ✅ Prevenci chyb - nemůžeš omylem zavolat funkci se špatným typem
• ✅ Dokumentaci - hned vidíš, co funkce přijímá a vrací
• ✅ IntelliSense - editor ti pomůže s parametry

Rozdíl JS vs TS

JavaScript:

• Rekurze funguje bez typů
• Můžeš omylem zavolat s nesprávnými parametry
• Flexibilnější, ale nebezpečnější
• Chyby odhalíš až při běhu

TypeScript:

• Rekurzivní funkce mají jasné typy
• TypeScript zkontroluje typy při kompilaci
• Nemůžeš omylem předat špatný typ
• Bezpečnější, lépe čitelné

// JavaScript - projde, ale způsobí problém
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
factorial("5");  // Runtime error! String * číslo = NaN

// TypeScript - editor tě upozorní
function factorial(n: number): number {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
factorial("5");  // ❌ Error: Argument of type 'string' is not assignable to parameter of type 'number'

Tip

💡 VŽDY měj základní případ (base case):

// ❌ CHYBA - nekonečná rekurze (chybí základní případ)
function bad(n) {
  return n + bad(n - 1);  // Nikdy se nezastaví!
}
// Výsledek: Stack overflow!

// ✅ SPRÁVNĚ - základní případ zastaví rekurzi
function good(n) {
  if (n === 0) return 0;  // Základní případ
  return n + good(n - 1);
}

💡 Rekurze vs smyčka - kdy použít co:

// ✅ Rekurze - pro stromové struktury, přirozené řešení
function traverseTree(node) {
  console.log(node.value);
  node.children.forEach(child => traverseTree(child));
}

// ✅ Smyčka - pro jednoduché opakování, lepší výkon
function sumLoop(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

💡 Pozor na hloubku rekurze (stack overflow):

// ⚠️ Nebezpečné - hluboká rekurze
factorial(10000);  // Stack overflow!

// ✅ Bezpečnější - iterativní přístup pro velká čísla
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}