Rekurzia alebo aby ste pochopili rekurziu, musíte najprv pochopiť rekurziu¶
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
}