Rekurze, rozděl a panuj, dynamické programování

BI-SPOL.21-21
  • Rekurzivní rozklad problému na podproblémy pomocí Rozděl a Panuj
  • Rekurze vs iterace
  • Dynamické programování

Úvodní myšlenka

  • Rekurze je programátorský nástroj (funkce volá samu sebe)
  • Rozděl a panuj a Dynamické programování jsou dvě různé strategie (paradigmata) návrhu algoritmů, které tento nástroj využívají k rozkladu problému na podproblémy
  • Zásadní rozdíl mezi nimi je v tom, zda jsou ty podproblémy nezávislé (Rozděl a panuj), nebo se překrývají (Dynamické programování)

Rekurze vs. iterace

Rekurze

  • Funkce, která v sekvenci příkazů volá sama sebe s jinými (menšími) parametry

  • Musí existovat ukončovací podmínka, která zastavuje větvení

  • Pracuje směrem shora-dolů

  • Každé rekurzivní volání vytváří rámec na zásobníku (Stack Frame), do něj se ukládají lokální proměnné, parametry a návratová adresa

  • Pokud je rekurze příliš hluboká, může dojít k zaplnění zásobníku a program spadne (Stack Overflow)

  • Lze vždy převést na iteraci

Lineární rekurze (Linear Recursion)

  • Nejzákladnější forma

  • Funkce v těle volá sama sebe nejvýše jednou (případně obsahuje více disjunktních volání, ale volá se jen jedno z nich)

  • Až narazí na ukončovací podmínku, začne se výsledek "probublávat" směrem zpátky

  • Časová složitost: - Funkce se zavolá lineárně -krát a v každém kroku provádí konstantní množství práce (jedno násobení/sčítání)

  • Paměťová složitost: - Kvůli odloženým operacím se na zásobníku (Stacku) musí vytvořit a držet rámců nad sebou

int faktorial(int n) {
    if (n <= 1) return 1;    // Ukončovací podmínka
    return n * faktorial(n - 1); 
}

Koncová rekurze (Tail Recursion)

  • Speciální poddruh lineární rekurze

  • Nastává tehdy, když je rekurzivní volání úplně poslední operací, kterou funkce provádí, nečeká se další "odložené" operace

  • Výsledek poté "neprobublává" zpátky, výsledek posledního volání je rovnou výsledkem celé funkce

  • Snadno převeditelná na iteraci (ale rekurzivní zápis bývá "čistší" a přehlednější v kódu)

  • Časová složitost: - Počet kroků a volání je identický jako u lineární rekurze

  • Paměťová složitost:

    • Teoreticky - Chová se jako lineární
    • Prakticky - Díky optimalizaci kompilátoru (Tail Call Optimization), kompilátor nepřidává nové rámce na zásobník, pouze přepisuje ten stávající
// Průběžně si taháme výsledek s sebou v akumulátoru, na konci ho stačí jen vrátit

int faktorial(int n, int akumulator) {
    if (n <= 1) return akumulator;            // Vrátí rovnou konečný výsledek
    return faktorial(n - 1, n * akumulator);  // Čisté koncové volání
}

Stromová / Kaskádní (Tree Recursion)

  • Nastává tehdy, když funkce v rámci jednoho průchodu tělem zavolá sama sebe více než jednou

  • Obvyklé pro přístup Rozděl a panuj, stromové a grafové průchody

  • Časová složitost: Typicky exponenciální (např. u naivního Fibonacciho) - s každým krokem se počet volání zdvojnásobuje (či obecně násobí)

  • Paměťová složitost: Maximální hloubka stromu, typicky tedy nebo

    • Stack totiž nedrží celý strom najednou, ale vždy jen aktuálně procházenou větev odshora dolů
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2); // Dvě rekurzivní volání!
}

Iterace

  • Opakování instrukcí pomocí smyček (for, while)

  • Musí existovat ukončovací podmínka, která zastaví cyklus (buď v deklaraci cyklu, nebo např. break;)

  • Pracuje směrem zdola-nahoru - od jednoduchého problému k celému

  • Režie na paměť je konstantní - nepřidávají se žádné nové Stack Frames, pouze se mění hodnoty stávajících proměnných

Rozděl a panuj

  • Metoda řešení problému rozložením na nezávislé podproblémy řešené stejným způsobem

  • Využívá rekurzi

    • Známe řešení triviální instance problému
    • Celkové řešení sestavíme z řešení podproblémů

  • Často klasické operace s binárními stromy (BVS, AVL), binární vyhledávání, MergeSort, QuickSort. QuickSelect, ...

  • Výhody: Úspornost zápisu kódu, přirozenost, intuitivnost (explicitní pojmenování toho, co se opakuje v menším) a expresivnost (snadné vyjádření složitosti)

  • Tři fáze algoritmu:

    • Rozděl (Divide) - Rozděl problém na několik menších podproblémů stejného typu
    • Panuj (Conquer) - Vyřeš tyto podproblémy
    • Zkombinuj - Spoj výsledky podproblémů do výsledného celkového řešení

  • Analýza časové složitosti

    • Lze využít Mistrovskou metodu známou z MA2
    • = počet podproblémů
    • = velikost každého podproblému
    • = režie na rozdělení a spojení

Typické příklady

Hanojské věže

https://courses.fit.cvut.cz/BI-MA2/@master/textbook/sec_lrr_uvod.html#subsec_hanoj

  • Problém:

    • Přesun věže o discích z kolíku na s využitím pomocného kolíku
    • Přičemž větší disk nesmí nikdy ležet na menším

  • Řešení:

    • Triviálně umíme přesunout:
      • disk = přesuneme z
      • disky = přesuneme vrchní na , ten spodní největší z , pak
    • Větší počet disků řešíme rozdělením:
      • (vrchních) disků přesuneme
      • (spodní největší) disk přesuneme
      • disků přesuneme zpět

Karacubův algoritmus násobení

Průvodce labyrintem algoritmů - sekce 9.3, strana 111
Záznam od Elišky v čase 5:32
(Karacuba, Karatsuba)

  • Problém:

    • Chceme vynásobit dvě obří -ciferná čísla a
    • Rozdělíme je na horních a dolních cifer, tedy pro nějaká -ciferná čísla
    • Součin by tedy šel zapsat jako
    • Nabízí se vypočítat 4 násobení
    • Časová složitost: , tedy

  • Řešení

    • Využijeme toho, že
    • K dostání původní červené závorky stačí přebývající členy odečíst
    • Tedy původní součin lze zapsat jako
    • Tím jsme místo 4 násobení využili jen 3 násobení a 2 sčítání
    • Časová složitost: , tedy

../../Attachments/Pasted image 20260609180139.png

Dynamické programování

  • Navazuje tam, kde Rozděl a panuj selhává z důvodu neefektivity

  • Používá se tehdy, když se problémy překrývají / opakují

  • Memoizace

    • Zapamatování výsledků již spočtených podproblémů, které se mohou znovu použít příště - "cache"
    • Výrazně redukuje počet potřebných operací

  • Princip dynamického programování

    1. Formulace problému rekurzivním rozkladem
    2. Identifikace opakovaných výpočtů podproblémů
    3. Vytvoření prázdné tabulky hodnota (cache)
    4. Vložení hodnot triviálních řešení do tabulky
    5. Před výpočtem podproblému se podíváme do tabulky
      1. Pokud je již vypočtené, použijeme tuto hodnotu
      2. Pokud není, vyřešíme pomocí rekurze
    6. Po návratu z rekurze zapíšeme výsledek do tabulky

Typy dynamického programování

Top-Down

  • Využívá rekurzi
  • Začíná voláním seshora, vždy se dívá do "cache", jestli už dílčí problém není vypočítán dříve

Bottom-Up

  • Využívá iteraci (cykly)
  • Není zde žádná rekurze, pouze obyčejné for / while
  • Začíná zdola od primitivních řešení, další výsledky staví na výsledcích předchozích

Typické příklady

Fibonacciho posloupnost

Fibonacciho posloupnost je definována následovně:

  • Problém:

    • Výpočty dílčích podproblémů se stále opakují
    • Např. pro výpočet potřebujeme spočítat a
    • Ale pro výpočet potřebujeme také spočítat , počítá se tedy duplicitně
    • ...

  • Řešení:

    • Podproblém spočítáme jen jednou, příště při zanoření rekurze využijeme cacheovanou hodnotu (řešení typu Top-Down)
    • ../../Attachments/Pasted image 20260609170535.png

Nejdelší rostoucí podposloupnost

  • Problém

    • Máme pole čísel, chceme podposloupnost (i s mezerami) takovou, aby byla rostoucí a zároveň co nejdelší
    • Nehledáme samotnou posloupnost, zajímá nás pouze délka
    • Představme si pole vstup[] = [10, 22, 9, 33, 21, 50, 41, 60, 80]
      • Rostoucí podposloupnost je např. [10, 22, 33, 50] (délka 4)
      • Jiná je např. [9, 21, 41, 60, 80] (délka 5)
      • Nejdelší je [10, 22, 33, 41, 60, 80] nebo [10, 22, 33, 50, 60, 80] (délka 6)
    • Zavoláme na každý prvek funkci, která nám vrátí nejdelší posloupnost z tohoto prvku

  • Řešení

    • Vytvoříme pomocné "cache" pole cache[] o stejné délce jako původní pole
    • Každé číslo samo o sobě tvoří podposloupnost o délce 1, vyplníme ho tedy samými jedničkami (řešení typu Bottom-Up)
    • Procházíme cache[] zleva doprava
      • Pro každý prvek zkontrolujeme všechny předchozí , tedy kde
      • Pokud vstup[i] > vstup[j], zkusíme podposloupnost prodloužit cache[i] = max( cache[i], cache[j]+1 )
    • Výsledkem je maximální hodnota v celém poli cache[]
int lis(vector<int> const& vstup) {

    int n = vstup.size();
    vector<int> cache(n, 1); // Stejná velikost jako vstup, naplněno samými jedničkami
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (vstup[j] < vstup[i])
                cache[i] = max(cache[i], cache[j] + 1); // Využití minulých hodnot (DP)
        }
    }

    int vysledek = cache[0];
    for (int i = 1; i < n; i++) { // Nalezení maximální hodnoty v poli
        vysledek = max(vysledek, cache[i]);
    }
    
    return vysledek;
}

Vytvořeno: 27. 5. 2026, 12:00
Poslední aktualizace: 9. 6. 2026, 18:07