Rekurzia alebo aby ste pochopili rekurziu, musíte najprv pochopiť rekurziu

rekurzia

Rýchlo k veci

  • Čo je to rekurzívna funkcia?
    • je to funkcia, ktorá volá samú seba
  • Bude to fungovať? Veď to nikdy neskončí
    • áno, pobeží donekonečna, a preto potrebuje mať rekurzívna funkcia podmienku, pri ktorej sa prestane volať

Ako si to predstaviť?

Predstavte si, že ste v kine. Všetci sú už usadení a rad je taký dlhý, že na jeho koniec nedovidíte. Ako zistíte na akom mieste sedíte?

Jeden zo spôsobov je, spýtať sa prisediaceho na akom mieste sedí on a potom len prirátať svoje miesto. Čo ak ale ani on nevie na akom mieste sedí? Spraví presne to isté čo my. Spýta sa prisediaceho, pripočíta svoje miesto a potom nám povie odpoveď. Takto môžu pokračovať až kým sa nenájde niekto, kto si je svojím miestom istý. Napríklad divák na začiatku radu, keďže on si svoje miesto poľahky odpočíta.

V tomto priklade by funkcia bola, zisťovanie miesta. Prestala volat pri cloveku na konci radu.

Príklady v programovaní

Faktoriál

Faktoriál čísla n je súčin všetkých celých čísel od 1 po n. Napriklad faktoriál 5 je 1 * 2 * 3 * 4 * 5. Funkcia na výpočet faktoriálu cisla n by mohla vyzerať nasledovne:

funkcia faktorial(n):
    if n <= 1 {
        return 1
    }
    else {
        return n * faktorial(n - 1)
    }

Prehľadávanie pričinkov

Chceme spočítať všetky súbory v priečinku a jeho podpriečinkoch. Štruktúra priečinkov je:

priečinok
├── podpriečinok1
│   ├── priecinok3
│   ├── súbor2.txt
│   └── súbor3.txt
├── podpriečinok2
│   └── súbor4.txt
├── súbor1.txt
└── súbor2.txt

Program:

funkcia spocitaj_subory(priecinok) {
    n = 0
    for polozka in priecinok {
        if polozka je súbor {
            n++
        }
        if polozka je priecinok {
            n += spocitaj_subory(priecinok)
        }
    }
    return n
}

Počítanie výskytu

V premennej mame string. Radi by sme spocitali, kolko krat sa v nom nachadza znak X.

funkcia rataj_x(string) {
    n = 0
    if prvy znak stringu == X {
        n += 1
    }
    n += rataj_x(string minus prvy znak)
    return n
}

Kontrola palindrómu

Palindróm je taký reťazec, ktorý sa číta rovnako zprava doľava aj zľava doprava

funkcia je_palindrom(retazec) {
    if dlzka retazca <= 1 {
        return ano
    }
    if retacez[posledny znak] == retacez[prvy znak] {
        odrezem prvy a posledny znak z retazca
        if je_palindrom(orezany retazec) {
            return ano
        }
    }
    return nie
}

Úlohy

Využite rekurziu v následujúcich príkladoch:

Ako to funguje pod kapotou nájdete v ksp kuchárke