Prednáška 9

Oznamy

Domáca úloha do piatku

• Časť bodov môžete dostať aj za neúplný program
• Na doplnkových cvičeniach vám môžeme poradiť, ak máte otázky, ale nenechávajte všetku prácu na poslednú chvíľu

Cvičenia

• Dnes pribudne do cvičení ďalší príklad na rekurziu, v piatok bonusová rozcvička za jeden bod
• Študentom, ktorí ešte nepracovali s rekurziou, silne odporúčame prísť na doplnkové cvičenia v piatok.

Klasické úvodné príklady na rekurziu

Rekurzia je metóda, pri ktorej definujeme objekt (funkciu, pojem, . . . ) pomocou jeho samého.

Na začiatok sa pozrieme na klasické príklady algoritmov využívajúcich rekurziu.

Výpočet faktoriálu

Faktoriál prirodzeného čísla n značíme n! a je to súčin všetkých celých čísel od 1 po n. Pre úplnosť 0! definujeme ako 1.

Výpočet pomocou cyklu z prednášky 3:

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Rekurzívna definícia faktoriálu:

• n! = 1 ak n≤1
• n! = n ⋅ (n-1)! inak

Túto matematickú definíciu môžeme priamočiaro prepísať do rekurzívnej funkcie:

int factorial(int n) {
    if (n <= 1) return 1;
    else return n * factorial(n-1);
}

Aby sa rekurzia nezacyklila, mali by sme dodržiavať nasledujúce zásady:

• Rekurzívna funkcia musí obsahovať vetvu pre triviálny prípad niektorého vstupu. Táto vetva nebude obsahovať rekurzívne volanie funkcie, ktorú práve definujeme.
• Rekurzívne volanie funkcie by malo mať vhodne redukovaný niektorý vstup, aby sme sa časom dopracovali k triviálnemu prípadu.

Najväčší spoločný deliteľ (Euklidov algoritmus)

Ďalším tradičným príkladom na rekurziu je počítanie najväčšieho spoločného deliteľa.

• Euklidov algoritmus z prednášky 3 bol založený na rovnosti gcd(a,b) = gcd(b, a mod b)
• Tú sme použili v cykle:

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Avšak opäť to isté môžeme ešte kratšie a elegantnejšie napísať rekurziou:

int gcd(int a, int b) {
   if (b == 0) return a;
   else return gcd(b, a % b);
}

Fibonacciho čísla

Nemôžeme vynechať obľúbený rekurzívny príklad - Fibonacciho čísla, ktoré sme videli na prednáške 4. Aj tam sa rekurzia priam pýta, keďže Fibonacciho čísla sú definované rekurzívne:

• F(0)=0
• F(1)=1
• F(n)=F(n-1)+F(n-2) pre n>=2

Z tejto definície vieme opäť urobiť rekurzívnu funkciu jednoducho:

int fib(int n){
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

Toto je opäť krajšie ako nerekurzívna verzia:

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        int F_posledne = 1;
        int F_predposledne = 0;
        for (int i = 2; i <= n; i++) {
            int F_n = F_posledne + F_predposledne;
            F_predposledne = F_posledne;
            F_posledne = F_n;                     
        }
        return F_posledne;
    }
}

Binárne vyhľadávanie

Aj binárne vyhľadávanie prvku v utriedenom poli z prednášky 7 sa dá pekne zapísať rekurzívne.

Pôvodná nerekurzívna funkcia vrátila polohu prvku x v poli a alebo hodnotou -1, ak sa tam nenachádzal:

int find(int a[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int index = (left + right) / 2;
        if (a[index] == x) {
            return index;
        }
        else if (a[index] < x) {
            left = index + 1;
        }
        else {
            right = index - 1;
        }
    }
    return -1;
}

V rekurzívnej verzii si okraje aktuálneho úseku poľa si v rekurzii posielame ako parametre:

int find(int a[], int left, int right, int x) {
    if (left > right) {
        return -1;
    }
    int index = (left + right) / 2;
    if (a[index] == x) {
        return index;
    }
    else if (a[index] < x) {
        return find(a, index+1, right, x);
    }
    else {
        return find(a, left, index - 1, x);
    }
}

Ak chceme vyhľadať x v poli a s n prvkami, voláme find(a, 0, n-1, x).

Na zamyslenie:

• Táto funkcia má dva triviálne (nerekurzívne) prípady. Ktoré?
• Aká veličina klesá v každom rekurzívnom volaní?

Tu je ešte trochu iná verzia binárneho vyhľadávania s niekoľkými rozdielmi:

• vraciame iba či sa x nachádza v poli alebo nie (dalo by sa rozšíriť aj na index)
• pri porovnávaní x a a[index] rozlišujeme iba dva prípady, nie tri
• končíme pri intervale dĺžky 1, nie 0

bool contains (int a[], int left, int right, int x){
    if (left == right) {
        return (a[left] == x);
    }
    int index = (left + right) / 2;
    if (x <= a[index]) {
        return contains(a, left, index, x);
    }
    else {
        return contains(a, index+1, right, x);
    }
}

int main(void) {
  const int n = 9;
  int a[n]={1,5,7,12,45,55,72,95,103};
  cout << contains(a, 0, n-1, 467) << endl;
  cout << find(a, 0, n-1, 467) << endl;
}

Zhrnutie

Pri rekurzii vyjadríme riešenie nejakej úlohy pomocou riešenia jednej alebo viacerých úloh toho istého typu, ale s menším vstupom plus ďalšie potrebné nerekurzívne výpočty

• výpočet n! vyjadríme pomocou výpočtu (n-1)! a násobenia
• výpočet gcd(a, b) vyjadríme pomocou výpočtu gcd(b, a % b)
• výpočet F[n] vyjadríme pomocou výpočtu F[n-1] a F[n-2]
• binárne vyhľadávanie v dlhšom intervale vyjadríme pomocou binárneho vyhľadávania v kratšom intervale

Všimnite si, že občas musíme zoznam parametrov nejakej funkcie rozšíriť pre potreby rekurzie

• napr. funkcia find by prirodzene dostávala pole a, dĺžku n a hľadaný prvok, ale kvôli rekurzii potrebuje ľavý a pravý okraj
• pre pohodlie užívateľa môžeme pridať pomocnú funkciu (wrapper):

int find(int a[], int n, int x) {
  return find(a, 0, n-1, x);
}

Viac o rekurzii

Nepriama rekurzia

• Všetky doteraz uvedené funkcie sú príkladom priamej rekurzie, kde definovaná funkcia používa seba samú priamo.
• V nepriamej rekurzii funkcia neodkazuje vo svojej definícii priamo na seba, ale využíva inú funkciu, ktorá sa odkazuje naspäť na prvú (všeobecnejšie sa kruh môže uzavrieť na viac krokov).
• Ako príklad uveďme rekurzívne testovanie párnosti a nepárnosti (len ilustračný príklad, párnosť zvyčajne testujeme pomocou n%2):

bool even(int n) {
    if (n == 0) return true;
    else return odd(n - 1);
}

bool odd(int n) {
    if (n == 0) return false;
    else return even(n - 1);
}

Rekurzia pomocou zásobníka - ako je rekurzia implementovaná

O rekurzívne volania sa stará zásobník volaní (call stack)

• Ide o všeobecnú štruktúru potrebnú aj v nerekurzívnych programoch s funkciami
• Po zavolaní nejakej funkcie f sa pre ňu vytvorí na zásobníku záznam, ktorý obsahuje všetky lokálne premenné a argumenty funkcie
• Keď potom z funkcie f zavoláme nejakú funkciu g (pričom v rekurzii môže byť aj f=g), tak sa vytvorí nový záznam pre g. Navyše v zázname pre f si uložíme aj to, v ktorom kroku sme prestali s výpočtom, aby sme vedeli správne pokračovať
• Po skončení výpočtu funkcie g sa jej záznam zruší zo zásobníka. Vrátime sa k záznamu pre funkciu f a pokračujeme vo výpočte so správnymi hodnotami všetkých premenných a od správneho miesta.

Záznamy v zásobníku si môžeme predstaviť uložené v stĺpci jeden nad druhým

• vrchný záznam je aktuálny, pre funkciu, ktorá sa vykonáva
• pod ním je záznam pre funkciu, ktorá ju volala atď
• na spodku je záznam pre funkciu main

Teraz si môžeme jednoduchý zásobník odsimulovať napríklad na výpočte faktoriálu.

int factorial(int n) {
    if (n < 2) return 1;
    else return n * factorial(n-1);
}

Zložitejšie príklady rekurzie

Každý z predchádzajúcich príkladov sme vedeli pomerne jednoducho zapísať aj bez rekurzie, aj keď rekurzívny výpočet bol často prehľadnejší, zrozumiteľnejší, kratší a krajší.

Ukážeme si však aj príklady, ktoré by sa bez rekurzie písali obtiažne (aj keď ako si neskôr ukážeme, rekurzia sa dá vždy odstrániť, v najhoršom prípade simuláciou zásobníka). Príklady, kde rekurzia veľmi pomáha, uvidíme na zvyšku dnešnej prednášky, ale aj na dvoch ďalších a k rekurzii sa vrátime aj neskôr v semestri a samozrejme na ďalších predmetoch.

Odbočka: korytnačia grafika v SVGdraw

Náš prvý dnešný príklad rekurzie budú rekurzívne obrázky, fraktály. Aby sa nám lepšie vykresľovali, v knižnici SVGdraw je možnosť kresliť pomocou korytnačej grafiky.

• Vytvoríme si virtuálnu korytnačku, ktorá má určitú polohu a natočenie.
• Môžeme jej povedať, aby sa otočila doľava alebo doprava o určitý počet stupňov (turtle.turnLeft(uhol) a turtle.turnRight(uhol)).
• Môžeme jej povedať, aby išla o určitú dĺžku dopredu (turtle.forward(dlzka))
• Keď ide korytnačka dopredu, zanecháva v piesku chvostom čiarku (vykreslí teda čiaru do nášho obrázku).

Napríklad na vykreslenie štvorca s dĺžkou strany 100 môžeme korytnačke striedavo prikazovať ísť o 100 dopredu a otáčať sa o 90 stupňov doľava.

• Na obrázku sa animuje pohyb korytnačky (pozri tu)
• Program by sa dal ľahko rozšíriť na vykresľovanie pravidelného n-uholníka (stačí zmeniť uhol otočenia a počet opakovaní cyklu)

#include "SVGdraw.h"

int main(void) {
    /* Vytvor korytnačku na súradniciach (25,175)
     * otočenú doprava na obrázku s rozmermi 200x200 pixelov,
     * ktorý bude uložený do súboru stvorec.svg. */
    Turtle turtle(200, 200, "stvorec.svg", 25, 175, 0);

    for (int i = 0; i < 4; i++) {
        turtle.forward(150);  /* vykresli čiaru dĺžky 100 */
        turtle.turnLeft(90);  /* otoč sa doľava o 90 stupňov */
    }
    /* strany sú vykreslené v poradí dolná, pravá, horná, ľavá */

    /* Ukonči vypisovanie obrázka. */
    turtle.finish();
}

Fraktály

Fraktály sú útvary, ktorých časti na rôznych úrovniach zväčšenia sa podobajú na celý útvar. Mnohé fraktály vieme definovať a vykresliť pomocou jednoduchej rekurzie.

Kochova krivka

Príkladom fraktálu je Kochova krivka. Ako vzniká?

• Predstavme si úsečku, ktorá meria d centimetrov.
• Spravíme s ňou nasledujúcu transformáciu:
  • Úsečka sa rozdelí na tretiny a nad strednou tretinou sa zostrojí rovnostranný trojuholník. Základňa trojuholníka v krivke nebude.
  • Dostávame tak útvar pozostávajúci zo štyroch úsečiek s dĺžkou d/3
• Tú istú transformáciu môžeme teraz spraviť na každej zo štyroch nových úsečiek, t.j. dostávame 16 úsečiek dĺžky d/9
• Takéto transformácie môžeme robiť do nekonečna

Druhá možnosť je popísať krivku pomocou dvoch parametrov: dĺžka d a stupeň n

• Kochova krivka stupňa 0 je úsečka dĺžky d
• Kochova krivka stupňa n pozostáva zo štyroch kriviek stupňa n-1 a dĺžky n/3
  • na presný popis umiestnenia a natočenia týchto kriviek nižšieho stupňa použijeme korytnačiu grafiku, čo máme spravené vo funkcii nižšie.

 
#include "SVGdraw.h"

void drawKoch(double d, int n, Turtle& turtle){
    if (n==0) turtle.forward(d);
    else {
        drawKoch(d/3, n-1, turtle);
        turtle.turnLeft(60);
        drawKoch(d/3, n-1, turtle);
        turtle.turnRight(120);
        drawKoch(d/3, n-1, turtle);
        turtle.turnLeft(60);
        drawKoch(d/3, n-1, turtle);
    }
}

int main(void) {
    int width = 310; /* rozmery obrazku */
    int height = 150;

    double d = 300; /* velkost krivky */
    int n = 5; /* stupen krivky */

    /* Vytvor korytnačku otočenú doprava. */
    Turtle turtle(width, height, "fraktal.svg", 1, height-10, 0);

    /* nakresli Kochovu krivku rekurzívne */
    drawKoch(d, n, turtle);

    /* Schovaj korytnačku. */
    turtle.finish();
}

Rekurzívny strom

A ešte jeden príklad fraktálu: strom definovaný nasledovne:

• strom má dva parametre: veľkosť d a stupeň n
• strom stupňa 0 je prázdna množina
• strom stupňa n pozostáva z kmeňa, ktorý tvorí úsečka dĺžky d a z dvoch podstromov, ktoré sú stromy stupňa n-1, veľkosti d/2 a otočené o 30 stupňov doľava a doprava od hlavnej osi stromu (pozri obrázky nižšie)

• 

  Strom stupňa 1

• 

  Strom stupňa 2

• 

  Strom stupňa 3

• 

  Strom stupňa 5

Rekurzívnu funkciu na vykresľovanie stromu napíšeme tak, aby sa po skončení vrátila na miesto a otočenie, kde začala

• Bez toho by sa sme nevedeli, kde korytnačka je po vykreslení ľavého podstromu a nemohli by sme teda kresliť pravý
• Korytnačka teda prejde po každej vetve dvakrát, raz smerom dopredu a raz naspäť (animácia)

#include "SVGdraw.h"

void drawTree(double d, int n, Turtle& turtle) {
    if (n == 0) {
        /* stupen 0 - nerob nic */
        return;  
    } else {
        /* kmen stromu */
        turtle.forward(d);              
        turtle.turnLeft(30);
        /* lava cast koruny */
        drawTree(d / 2, n - 1, turtle); 
        turtle.turnRight(60);
        /* prava cast koruny */
        drawTree(d / 2, n - 1, turtle); 
        turtle.turnLeft(30);
        /* navrat na spodok kmena */
        turtle.forward(-d);             
    }
}

int main(void) {
    /* rozmery obrazku */
    int width = 150; 
    int height = 200;

    /* velkost stromu */
    double d = 100; 
    /* stupen krivky */
    int n = 5; 

    /* vytvor korytnačku otočenú hore */
    Turtle turtle(width, height, "fraktal.svg", 
                  width / 2, height - 10, 90);

    /* nakresli strom rekurzívne */
    drawTree(d, n, turtle);

    /* schovaj korytnačku */
    turtle.finish();
}

Hanojské veže

• Problém Hanojských veží pozostáva z troch tyčí a niekoľkých kruhov rôznej veľkosti. Začína sa postavením pyramídy z kruhov (kameňov) na prvú tyč od najväčšieho po najmenší.
• Úlohou je potom presunúť celú pyramídu na inú tyč, avšak pri dodržaní nasledovných pravidiel:
  • v jednom ťahu (na jedenkrát) je možné premiestniť iba jeden hrací kameň
  • väčší kameň nesmie byť nikdy položený na menší

Úlohu budeme riešiť rekurzívne

• Ak máme iba jeden kameň, úloha je veľmi jednoduchá - preložíme ho z pôvodnej tyče na cieľovú tyč.
• Ak chceme preložiť viac kameňov (nech ich je N), tak
  • Všetky okrem posledného preložíme na pomocnú tyč (na to použijeme taký istý postup len s N-1 kameňmi)
  • Premiestnime najväčší kameň na cieľovú tyč
  • Zatiaľ odložené kamene (na pomocnej tyči) preložíme z pomocného na cieľovú tyč (na to použijeme opäť taký istý postup s N-1 kameňmi)

Aby sme to popísali konkrétnejšie - preloženie N kameňov z A na C (s pomocným stĺpikom B) urobíme takto:

• Preložíme N-1 kameňov z A na B (s použitím C)
• Preložíme jeden kameň z A na C (s použitím B - ale reálne to potrebovať nebudeme)
• Preložíme N-1 kameňov z B na C (s použitím A)

void presunHanoi(int odkial, int cez, int kam, int n) {
    if (n == 1) {
        cout << "Prelozim kamen z " << odkial 
             << " na " << kam << endl;
    } else {
        // odlozime n-1 na docasnu tyc cez
        presunHanoi(odkial, kam, cez, n-1); 
        // prelozime najvacsi kamen na finalnu tyc kam
        presunHanoi(odkial, cez, kam, 1);   
        // zvysnych n-1 prelozime z docasnej tyce na finalnu
        presunHanoi(cez, odkial, kam, n-1); 
    }
}

int main (void) {
    // z tyce 1 na tyc 3 (pomocou tyce 2)
    presunHanoi(1, 2, 3, 3); 
}

Dôležité je si uvedomiť, že nasledovný postup dodržuje pravidlá. Po zavolaní funkcie presunHanoi vždy platí:

• Funkcia bude presúvať n horných kameňov z tyče odkial na tyč kam pomocou pomocnej tyče cez.
• Ak n>1, tak na tyčiach kam a cez sú len väčšie kamene ako horných n kameňov na odkial.
• Ak n=1, na tyči kam sú len väčšie kamene, obsah tyče cez môže byť ľubovoľný.