# Rekurzia alebo aby ste pochopili rekurziu, musíte najprv pochopiť rekurziu ![rekurzia](_static/rekurzia.jpg) ## 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: - [Aké mám číslo](https://testovac.ksp.sk/tasks/ls18-miesto/) - [Palindróm](https://testovac.ksp.sk/tasks/ls18-palindrom/) ## Ako to funguje pod kapotou nájdete v [ksp kuchárke](https://www.ksp.sk/kucharka/rekurzia/) #### Zdroje - [ksp kuchárka](https://www.ksp.sk/kucharka/rekurzia/) - [Pripovnanie ku kinu](https://www.quora.com/How-should-I-explain-recursion-to-a-4-year-old)