La première leçon

Na této stránce se používá SVG a MathML.
Firefox je umí a některé další prohlížeče se pro ně dají upravit.

První cvičení

Rekurse

(Recursion)

Recurse je pro člověka mnohem přirozenější než rekurence či cykly.
V minulm semestru jsme si leccos (například binarySearch) rekursivně vysvětlovali.
Pro nás je rekurse jednodušší. Pro počítače je zase náročnější. Původně rekursi dokonce ani neuměly.
I tam, kde je to jedno, bychom stejně měli umět převádět rekursi na rekurenci a obráceně rekurenci na rekursi.
Rekursi si ukážeme u následující chůze po schodech:

Zadání pro práci v tomto cvičení:

Napište rekursivně program pro výpočet faktoriálu (bylo na přednášce, ale zkuste sami).
Napište rekursivně program pro výpočet největšího společného dělitele Eukleidovým algoritmem
(bylo na přednášce, ale zkuste sami).
Napište rekursivně program pro výpočet Fibonacciho posloupnosti(bylo na přednášce,
ale zkuste sami).

Prémiové přizadání

Zobecníme-li si předchozí tři případy, můžeme rekursivní funkci jednoho typu popsat následovně:

	f(x):
		x ∈ M ⇒ return d(x);
		return g(f(h₁(x)), f(h₂(x)), … f(h_n(x)));
		nebo
		return g(x, f(h₁(x)), f(h₂(x)), … f(h_n(x)));

kde pro x ∉ M musí splňovat h_*(h_*(h_*(x)…)) ∈ M,
a funkce h se volá konečněkrát.

Vyskytuje-li se v g více než jednou f, pak se výpočet „košatí” exponenciálně ‑ což určitě býval problém
a dokonce i dnes může být.
Následuje příklad divnoFunk.c, která nedává žádný smysl ‑ jen ilustruje předchozí schéma.

#include <stdlib.h>
#include <stdio.h>
#include <math.h>


unsigned int isinM(unsigned int x);
unsigned int d(unsigned int x);
unsigned int h1(unsigned int x);
unsigned int h2(unsigned int x);
unsigned int h3(unsigned int x);
unsigned int g(unsigned int x, unsigned int y, unsigned int z);
unsigned int f(unsigned int x);

int main()
{
    unsigned int xx, i;
    printf("Zadejte do ktereho argumentu se ma spocitat: ");
    scanf(" %u", &xx);
    for (i = 1; i <= xx; ++i) {
        printf("f(%2u) = %u\n", i, f(i));
    }       
}


unsigned int isinM(unsigned int x)
{
    return x == 1 || x == 2 || x == 3 || x == 6 || x == 7 || x == 11 || x == 13 || x == 16 || x == 19 || x == 26;
}

nsigned int d(unsigned int x)
{
    return 97 - x;
}

unsigned int h1(unsigned int x)
{
    return x < 7 ? x + 1 : x / 2;
}

unsigned int h2(unsigned int x)
{
    return x > 49 ? (unsigned int)sqrt((double)x) : x / 3;
}

unsigned int h3(unsigned int x)
{
    return x < 28 ? x + 2 : (2 * x) / 3;
}

unsigned int g(unsigned int x, unsigned int y, unsigned int z)
{
    return (x + y + z) / 4;
}

unsigned int f(unsigned int x)
{
    if (isinM(x)) return d(x);
    return g(f(h1(x)), f(h2(x)), f(h3(x)));
}

V dalším budeme vidět, že existují i jiné typy rekursivních funkcí, kde je více vstupních parametrů etc.
Vždy ale musíme napřed zajistit ukončení rekurse, a teprve potom může funkce volat sama sebe.

Naprogramujte rekursivně Binární vyhledávání (vysvětlovalo se rekursivně a probíralo se s cyklem v podzimním semestru).
Možno nakouknout

Naprogramujte výpočet kombinačního čísla (střední škola) rekursivně.
Použijte buď definici, ale s vykrácením konce faktoriálu v čitateli a (n - k)! ve jmenovateli;
anebo vlastnosti:

{{\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}+{\binom {n-1}{k}}"

, využijte symetrie

{\binom {n}{k}}={\binom {n}{n-k

a nebo či skutečnosti, že

{\binom {n}{0}}={\binom {n}{n}}

= 1.

/**
 * @file  combiNum.c
 *
 * @author   Ales  Zlamal
 */
 
#include <stdlib.h>
#include <stdio.h>

/**
  * Pocita kombinacni cislo „n nad k“ (c(n, k))
  *
  * @param  n
  * @param  k
  * @return  kombinacni cislo c(n, k)
  */
unsigned int c(unsigned int n, unsigned int k);


int main()
{
    unsigned int n, nn, k;
    printf("Zadejte kolik radku Pascalova trojuhelnika se ma vytisknout: ");
    scanf(" %u", &nn);
    for (n = 0; n <= nn; ++n) {
        printf("%*s", 58 - 3 * n, " ");
        for (k = 0; k <= n; ++k) {
           printf("   %3u", c(n, k));
        }
        printf("\n");
    }
    return EXIT_SUCCESS;
}

Naprogramujte funkci vyjádřující zadanou hodnotu v pravidelné posiční soustavě o zadaném základu
se opět probíralo na prvním cvičení podzimního semestru a bylo i na testech) rekursivně
a oproti podzimnímu semestru s číslicemi ve správném pořadí.
Dobře napsaná rekursivní verse nám to umožní.
Pro zapomětlivé.
Naprogramujte rekursivně funkci počítající odmocninu algoritmem, jenž se připisuje Newtonovi ‑ opět jsme ho probírali
na prvním cvičení podzimního semestru.
Osvěžit si.

Při vypočtu hodnoty π Gaussovým‑Legendrovým algoritmem se používá dvojposloupnost:

a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}.

{\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\\\b_{n+1}&={\sqrt {a_{n}b_{n}}}

lim_{n \to \infty} a_{n} = lim_{n \to \infty} b_{n}

{\sqrt{2}}

je v math.h M_SQRT1_2, ale ne vždy a všude to funguje.

Naprogramujte rekursivně nalezení hodnoty společné limity obou posloupností s co největší přesností.

Tady jsem v pokušení parafrázovat bajku o dvou medvědech, kole sýra a lišce. (Oscar Wild napsal „Odolám všemu krom pokušení.” a „Nejlepší způsob jak odolat pokušení je podlehnout mu.” a řídil se tím a pobyl si ve vězení: The Ballad of Reading Gaol.)

Bez bajky napíši zadání: napište rekursivní program na iterpolaci funkce (analogie binárního vyhledávání či „výpočtu” √ podle předpředešlého zadání) pro rozdělení kruhu tětivou na dvě kruhové výseče s obsahy v poměru 2 : 1.
Tětiva je úsečka ≡ průnik sečny kružnice a jí vymezeným kruhem. Jinak: Tětiva je úsečka s koncovými body tam, kde sečna protíná kružnici.

Na obrázku vpravo úsečka q je vzdálenost středu S od tětivy.

Na onom obrázku vpravo je v jednotkovém kruhu tětiva červeně a hledáme v něm poměr velikosti (v jednotkovém kruhu) zelené úsečky : 1, při výpočtu nám tedy vychází jakožto část jednotky.

(Hledáme vlastně hodnotu inversní funkce k analytické funkci pro výpočet obsahu kruhové úseče při zadaném q.)

Ona funkce, jejíž hodnotu hledáme, musí být ‑ stejně jako při binárním hledání ‑ monotonní. V našem případě je klesající: s rostoucí vzdáleností tětivy od středu kruhu se obsah úseče zmenšuje ‑ funkce klesá. Krajní body intervalu, v němž hledáme, jsou v jednotkovém kruhu (pochopitelně) 0 a 1.

Počítejte použitím typu double a potřebovat budete funkce z math.h acos (arc cos) a sqrt (

\sqrt{}

), Pythágorovu větu a z math.h M_PI (π) (tohle ale ne vždy a všude to funguje. Pokud program sestavujete (a překládáte) z příkazového řádku, nezapomeňte na jeho konci přidat „-lm”.
Toto zadání je poněkud matematičtější. Nemáte zapomenout, že jste matematici, a že i při programování se mohou a mají používat matematické „buňky”.

Co jste (z předepsaných úkolů) nezvládli na cvičení, dodělejte mimo něj (například doma).

V úterý 27. února 2024 večer zpřístupním své verze požadovaného.

Obecně platí, že rozmyslet si a naprogramovat problém rekursivně je jednodušší než nerekursivně.
Také je pravda, že rekurse je pro počítače náročnější ‑ někdy hodně.
S rychlostmi a paměťovou kapacitou současných počítačů jednoznačně upřednostňujeme lidský faktor před nelidským.

Někdy (často) ale bývá jednodušší formulovat algoritmus nerekursivně ‑ příkladem:
Příprava krupičné kaše::
krupičnou kaši vaříme ‑ vystavujeme ji teplu na držení teploty varu ‑ míchajíce ji
dokud
nedosáhne požadované hustoty.

Dále uvádím několik příkladů zhúvěřilého použití rekurse:

Test prvočíselnosti (opět a důkladně se probíralo v podzimním semestru).
Toto je poněkud náročnější. Musí se zadávat i dělitel.

/**
 * @file  isPrime.c
 *
 * @author   Ales  Zlamal
 */
 
#include <stdlib.h>
#include <stdio.h>

/**
 * Pocita prirozeneciselnou odmocninu === celky z odmocniny (|_\|x)_|)
 *
 * @param a  cislo z nejz odmocnina pocita
 * @return  nejvetsi prirozene cislo mensi nebo rovne odmocnine z a
 */
unsigned int isqrt(unsigned int a);         /*  m = isqrt(as) */

/**
 * Testuje prvociselnost (cisla x: isPrime(x, 0)) od odmocniny z x a jen prvocisly (Eratosthenes)
 * 
 * @param   x testovane cislo
 * @param   d  delitel
 * @return  1, jestlize je zadane cislo prvocislo; neni-li zadane cislo prvocislo, 0
 */
unsigned int isPrime(unsigned int x, unsigned int d);

int main()
{
    unsigned int xx, ii;
    printf("Zadejte mez prvociselneho testu (0 program ukoncuje): ");
    scanf(" %u", &xx);
    if (xx == 0) return EXIT_SUCCESS;
    printf("Prvocisla:\n");
    for (ii = 0; ii <= xx; ++ii) {
        if (isPrime(ii, 0)) {
            printf("%3u\n", ii);
        }
    }
    printf("\n\nNeprvocisla:\n");
    for (ii = 0; ii <= xx; ++ii) {
        if (!isPrime(ii, 0)) {
            printf("%3u\n", ii);
        }
    }
}


unsigned int isqrt(unsigned int a)
{
    unsigned int m, p, q, t, u;
    p = 1; 
    q = 1; 
    u = 3;
    p <<= sizeof(unsigned int)*8 - 2;
    q <<= sizeof(unsigned int)*4 - 1;
    u <<= sizeof(unsigned int)*8 - 2;
    while(
        (a & u) == 0
    ){
        u >>= 2;
        p >>= 2;
        q >>= 1;
    }
    a -= p;
    t = p;
    u = p;
    m = q;
    while(
        (a != 0) && (t > 0x00000002)
    ){
        q >>= 1;
        p >>= 1;
        t >>= 2;
        if(
            a >= (u | t)
        ){
        a -= t;
        a -= u;
            u |= p;
        m |= q;
        }
        p >>= 1;
        u >>= 1;
    }
    return m;
}

unsigned int isPrime(unsigned int x, unsigned int d)
{
    if (x < 2) return 0;
    if (x < 4) return 1;
    if (d == 0) return isPrime(x, isqrt(x));
    if (d == 1) return d;
    if (isPrime(d, 0) && x % d == 0) return 0;
    return isPrime(x, d - 1);
}

Kdyby dělení ‑ respective výpočet zbytku po dělení ‑ bylo (časově) „drahé“ (kdysi to byl tisícinásobek času sčítání) a zjišťování prvočíselnosti (do √ z testovaného čísla) (například nalezením v tabulce nebo v rychlé implementaci množiny) „levné“, pak by efektivita takového výpočtu dávala smysl. Je-li ale výpočet zbytku po dělení stejně dlouhý jako sčítání a prvočíselnosti (do √ z testovaného čísla) naopak podstatně delší, nemá smysl dělit jen prvočísly (u dělitelů zjišťovat prvočíselnost).
Zkuste upravit na testování dělitelnosti všemi čísly ‑ nejen prvočísly.

Následují rekursivní verse tří třídících algoritmů velmi důkladně se probíralo v podzimním semestru v předmětu Úvod do programování I (M1160)

Bubble sort (bublinkové třídění).

/**
 * @file bubbleSort.c
 * 
 * @author   Ales  Zlamal
 */ 

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

/**
 * Generuje do pole od zadaneho indexu po zadany index hodnoty ze zadaneho (uzavreneho) intervalu
 *
 * @param  d   pole, do ktereho se nahodne ciselne hodnoty generuji 
 * @param  hodnotaOd   levy kraj (uzavreneho) intervalu, z nejz se generuji nahodne ciselne hodnoty 
 * @param  hodnotaPo   pravy kraj (uzavreneho) intervalu, z nejz se generuji nahodne ciselne hodnoty 
 * @param  odkud   levy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 * @param  pokud   pravy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 */
void generujNahodne(int* d, int hodnotaOd, int hodnotaPo, int odkud, int pokud);

/**
 * Generuje do pole od zadaneho indexu po zadany index hodnoty ze zadaneho (uzavreneho) intervalu
 *
 * @param  e   pole, do ktereho se nahodne ciselne hodnoty generuji 
 * @param  odkud   levy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 * @param  pokud   pravy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 */
void printPole(int* e, int odkud, int pokud);

/**
 * Prohod sousedni, je-li treba 
 *
 * @param b  pole, v kterem se ciselne hodnoty - posloupnost - tridi (vzestupne)
 * @param i  index prvku, ktery se porovnava se svym bezprostrednim naslednikem, a prohazuji se, je-li treba
 * @return r  priznak inverse, tj. ze se prohodilo 
 */
int pjt(int* b, int i, int r);

/**
 * Vzestupne setridi algoritmem Bubble sort s ukoncenim nebyla-li v bublani zadna inverse (a tedy vymena) 
 *
 * Vola se bubbleSort(pole, index prvniho, index posledniho, 0);
 *
 * @param c  pole, v kterem se ciselne hodnoty - posloupnost - tridi (vzestupne)
 * @param i  index prvku, odkud se probublava
 * @param k  index posledniho prvku v poli - podposloupnosti - po ktery se ma probublavat
 * @param r  priznak inverse, tj. ze se prohodilo
 */
void bubbleSort(int* c, int j, int k, int r);

#define N 26

int main()
{
    int i, a[N];

    srand(time(NULL));
    generujNahodne(a, 0, 99, 0, N - 1); 
    printPole(a, 0, N - 1);
    bubbleSort(a, 0, N - 1, 0);
    printPole(a, 0, N - 1);
    return 0;
}


void generujNahodne(int* d, int hodnotaOd, int hodnotaPo, int odkud, int pokud)
{
    if (odkud == pokud) return;
    d[odkud] = hodnotaOd + rand() % (hodnotaPo - hodnotaOd + 1);
    generujNahodne(d, hodnotaOd, hodnotaPo, odkud + 1, pokud);
}

void printPole(int* e, int odkud, int pokud)
{
    if (odkud == pokud) {
        printf("\n");
        return;
    }
    printf("%2d ", e[odkud]);
    printPole(e, odkud + 1, pokud);
}

int pjt(int* b, int i, int rr)
{
    int pom;
    if (b[i] > b[i+1]) {
        pom = b[i];
        b[i] = b[i+1];
        b[i+1] = pom;
        rr = 0;
    }
    return rr;
}

void bubbleSort(int* d, int j, int k, int r)
{
    if ((j == k) && r) return;
    if (j < k) {
        bubbleSort(d, j + 1, k, pjt(d, j, r));
    } else {      
        bubbleSort(d, 0, k - 1, 1);
    }
}

Zkuste napsat jeho sice rekursivní versi, ale s použitím nerekursivní funkce bublání
(postupné testovaní dvojic sousedních prvků a jejich prohození, je-li třeba, až kam je třeba).

Select sort (třídění výběrem).

/**
 * @file selectSort.c
 * 
 * @author   Ales  Zlamal
 */ 

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

/**
 * Generuje do pole od zadaneho indexu po zadany index hodnoty ze zadaneho (uzavreneho) intervalu
 *
 * @param  d   pole, do ktereho se nahodne ciselne hodnoty generuji 
 * @param  hodnotaOd   levy kraj (uzavreneho) intervalu, z nejz se generuji nahodne ciselne hodnoty 
 * @param  hodnotaPo   pravy kraj (uzavreneho) intervalu, z nejz se generuji nahodne ciselne hodnoty 
 * @param  odkud   levy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 * @param  pokud   pravy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 */
void generujNahodne(int* d, int hodnotaOd, int hodnotaPo, int odkud, int pokud);

/**
 * Generuje do pole od zadaneho indexu po zadany index hodnoty ze zadaneho (uzavreneho) intervalu
 *
 * @param  e   pole, do ktereho se nahodne ciselne hodnoty generuji 
 * @param  odkud   levy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 * @param  pokud   pravy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 */
void printPole(int* e, int odkud, int pokud);

/**
 * Prohod zadane, je-li treba 
 *
 * @param b  pole, v kterem se ciselne hodnoty - posloupnost - tridi (vzestupne)
 * @param i  index prvku, ktery se porovnava s druhym zadanym a prohazuji se, je-li treba
 * @param j  index prvku, ktery se porovnava s prvnim zadanym a prohazuji se, je-li treba
 */
void pjt(int* b, int i, int j);

/**
 * Vzestupne setridi algoritmem Select sort 
 *
 * @param c  pole, v kterem se ciselne hodnoty - posloupnost - tridi (vzestupne)
 * @param j  index prvku, ktery se porovnava se prvkem na indexu dosud nalezeneho maxima v podposloupnosti
 * @param k  index posledniho prvku nesetrideneho useku pole - podposloupnosti
 * @return  index maximalniho prvku z nesetrideneho useku pole - podposloupnosti
 */
int selectSort(int* c, int j, int k);

#define N 26

int main()
{
    int i, a[N];

    srand(time(NULL));
    generujNahodne(a, 0, 99, 0, N - 1); 
    printPole(a, 0, N - 1);
    selectSort(a, N-1, N-1);
    printPole(a, 0, N - 1);
    return 0;
}


void generujNahodne(int* d, int hodnotaOd, int hodnotaPo, int odkud, int pokud)
{
    if (odkud == pokud) return;
    d[odkud] = hodnotaOd + rand() % (hodnotaPo - hodnotaOd + 1);
    generujNahodne(d, hodnotaOd, hodnotaPo, odkud + 1, pokud);
}

void printPole(int* e, int odkud, int pokud)
{
    if (odkud == pokud) {
        printf("\n");
        return;
    }
    printf("%2d ", e[odkud]);
    printPole(e, odkud + 1, pokud);
}

void pjt(int* b, int i, int j)
{
    int pom;
    if (b[j] > b[i]) i = j;
    if (i != j) {
        pom = b[i];
        b[i] = b[j];
        b[j] = pom;
    }
}

int selectSort(int* c, int j, int k)
{
    int m;

    if ((j == 0) || (k == 0)) return 0;
    if (j < k) {
        m = selectSort(c, j - 1, k);
        return c[j] > c[m] ? j : m;
    }
    pjt(c, selectSort(c, k-1, k), k);
    selectSort(c, k-1, k-1);
    return 0;
}

Zkuste napsat jeho sice rekursivní versi, ale s použitím nerekursivní funkce výběru buď minima anebo maxima ‑ podle vašeho výběru.

Insert sort (třídění zatřizováním).

/**
 * @file insertSort.c
 * 
 * @author   Ales  Zlamal
 */ 

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

/**
 * Generuje do pole od zadaneho indexu po zadany index hodnoty ze zadaneho (uzavreneho) intervalu
 *
 * @param  d   pole, do ktereho se nahodne ciselne hodnoty generuji 
 * @param  hodnotaOd   levy kraj (uzavreneho) intervalu, z nejz se generuji nahodne ciselne hodnoty 
 * @param  hodnotaPo   pravy kraj (uzavreneho) intervalu, z nejz se generuji nahodne ciselne hodnoty 
 * @param  odkud   levy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 * @param  pokud   pravy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 */
void generujNahodne(int* d, int hodnotaOd, int hodnotaPo, int odkud, int pokud);

/**
 * Generuje do pole od zadaneho indexu po zadany index hodnoty ze zadaneho (uzavreneho) intervalu
 *
 * @param  e   pole, do ktereho se nahodne ciselne hodnoty generuji 
 * @param  odkud   levy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 * @param  pokud   pravy krajni index podpole, do nejz se generuji nahodne ciselne hodnoty 
 */
void printPole(int* e, int odkud, int pokud);

/**
 * Vzestupne setridi algoritmem Insert sort  
 *
 * Vola se insertSort(pole, index prvniho, index posledniho, velikost pole);
 *
 * @param c  pole, v kterem se ciselne hodnoty - posloupnost - tridi (vzestupne)
 * @param j  index prvku, odkud se zacina tridit
 * @param t  hodnota, ktera se zatrizuje 
 * @param k  index hodnoty, ktera se bude zatrizovat 
 * @param n  index konce trizene podposloupnosti + 1
 */
void insertSort(int* c, int j, int t, int k, int n);

#define N 26

int main()
{
    int a[N];

    srand(time(NULL));
    generujNahodne(a, 0, 99, 0, N - 1); 
    printPole(a, 0, N - 1);
    insertSort(a, 0, 0, 1, N);
    printPole(a, 0, N - 1);
    return 0;
}


void generujNahodne(int* d, int hodnotaOd, int hodnotaPo, int odkud, int pokud)
{
    if (odkud == pokud) return;
    d[odkud] = hodnotaOd + rand() % (hodnotaPo - hodnotaOd + 1);
    generujNahodne(d, hodnotaOd, hodnotaPo, odkud + 1, pokud);
}

void printPole(int* e, int odkud, int pokud)
{
    if (odkud == pokud) {
        printf("\n");
        return;
    }
    printf("%2d ", e[odkud]);
    printPole(e, odkud + 1, pokud);
}

void insertSort(int* c, int j, int t, int k, int n)
{
    if (k == n) return;
    if (j + 1 == k) {
        if (c[k] >= c[k-1]) { 
            insertSort(c, k, t, k + 1, n);
        } else { 
            t = c[k];
            c[k] = c[j];
            insertSort(c, j - 1, t, k, n);
        }
    } else {
        if ((j >= 0) && (c[j] > t)) {
            c[j+1] = c[j];
            insertSort(c, j - 1, t, k, n);
        } else {
            c[++j] = t;
            insertSort(c, k, t, k + 1, n);   
        }
    }
}

Zkuste napsat versi sice rekursivní, ale s použitím nerekursivní funkce zatřízení.