Programovanie (1) v C/C++
1-INF-127, ZS 2024/25

Úvod · Pravidlá · Prednášky · Softvér · Testovač
· Kontaktujte nás pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Prosíme študentov, aby si pravidelne čítali e-maily na @uniba.sk adrese alebo aby si tieto emaily preposielali na adresu, ktorú pravidelne čítajú.


Prednáška 9

Z Programovanie
Skočit na navigaci Skočit na vyhledávání

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.

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

Kochove krivky stupňov 0-5


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)

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ý.