Keď funkcia volá samu seba
Na úvod si vytvorme program, ktorý nám bude odpočítavať čas, napr. explózie bomby.
#include <iostream>
using namespace std;
void odpocet(int sekunda)
{
bool nadisielCas = false;
while(!nadisielCas)
{
if(sekunda > 0)
{
cout << "Do denotacie ostava: " << sekunda << " sekund!!!\n";
sekunda--;
}
else
{
cout << "Nastal vybuch!!!\n";
nadisielCas = true;
}
}
}
int main()
{
int casDoVybuchu = 10;
odpocet(casDoVybuchu);
return 0;
}
Vo výstupe programu vidíme postupné odpočítanie času výbuchu bomby a jej detonáciu.
Do denotacie ostava: 10 sekund!!! Do denotacie ostava: 9 sekund!!! Do denotacie ostava: 8 sekund!!! Do denotacie ostava: 7 sekund!!! Do denotacie ostava: 6 sekund!!! Do denotacie ostava: 5 sekund!!! Do denotacie ostava: 4 sekund!!! Do denotacie ostava: 3 sekund!!! Do denotacie ostava: 2 sekund!!! Do denotacie ostava: 1 sekund!!! Nastal vybuch!!!
V programe sme využili cyklus while, ktorý nám postupne odrátava čas detonácie bomby. Celá logika programu sa nachádza v našej definovanej funkcii odpocet(). Odpočet sme urobili iteratívne cez cyklus while.
Využitie funkcii nám kód často skracuje a spriehľadňuje. Avšak existuje jeden postup, ako robiť niektoré veci efektívnejšie. Zoznámte sa s rekurziou, čo nie je nič iné než volanie funkcie samej seba. Volanie sa uskutočňuje v tele volanej funkcie.
#include <iostream>
using namespace std;
void odpocet(int sekunda)
{
if(sekunda > 0)
{
cout << "Do denotacie ostava: " << sekunda << " sekund!!!\n";
odpocet(sekunda-1);
}
else
{
cout << "Nastal vybuch!!!\n";
return;
}
}
int main()
{
int casDoVybuchu = 10;
odpocet(casDoVybuchu);
return 0;
}
Využitím rekurzie môžeme častokrát výrazne skrátiť kód. V našom prípade sme sa zbavili cyklu while a pravdivostnej premennej nadisielCas. Treba však myslieť nato, že funkcia bude volať samu seba do nekonečná. Aby sme sa tomu vyhli, musíme za splnení istej podmienky ukončiť rekurzívnu funkciu.
Rekurzívny faktoriál
Väčšina seriálov o rekurzii začína s faktoriálom ako najvhodnejší príklad. My sme síce faktoriálom nezačali, ale ostaneme tradícii verný a ukážeme si rekurzívny faktoriál.
#include <iostream>
using namespace std;
int testFaktorial(int cislo)
{
if(cislo == 1)
return 1;
else
return cislo * testFaktorial(cislo-1);
}
int main()
{
int poleCisel[5] = {3,5,6,8,9};
for(size_t i = 0; i < sizeof(poleCisel)/sizeof(poleCisel[0]); i++)
{
cout << "Faktorial cisla "<<poleCisel[i]<< " je: "<<testFaktorial(poleCisel[i]) << "\n";
}
return 0;
}
Môžete porovnať rekurzívnu implementáciu faktoriálu s iteratívnou, ktorú sme implementovali v predchádzajúcom dieli. Pochopenie toho, čo sa deje pri rekurzívnom faktoriáli sa môže zdať komplikované. Skúsme si to to čo najjednoduchšie vysvetliť a uvidíte, že je to malina.
Skúsme postupne po volaniach napr. pri zisťovaní faktoriálu 3.
1.return – 3 * testFaktorial(3-1)
2.return – 2 * testFaktorial(2-1)
3.return – 1
Teraz ideme akože spätne. A to tak, že návratová hodnota funkcie testFaktorial(2-1) je 1. Následne sa vynásobí 2*1 a aktuálne vráti funkcia hodnotu 2. Nakoniec sa vynásobí 3*2 a dostaneme výsledok 6.
Na záver prvočísla
Pre zopakovanie, prvočísla sú také čísla, ktoré sú deliteľné 1 alebo sebou samými. Ukážeme si implementáciu prvočísel, ktorá využíva rekurziu.
#include <iostream>
#include <math.h>
using namespace std;
bool testPrvocislo(int cislo, int i)
{
if(i > sqrt(cislo))
return true;
else
{
if(cislo % i == 0)
return false;
else testPrvocislo(cislo,i+1);
}
}
int main()
{
int poleCisel[21] = {3,5,6,7,8,9,11,12,13,15,16,17,19,20,21,23,25,28,29,31,32};
for(int i = 0; i < sizeof(poleCisel)/sizeof(poleCisel[0]); i++)
{
cout << "Cislo "<<poleCisel[i];
if(testPrvocislo(poleCisel[i],2))
{
cout << " je prvocislo!" << "\n";
}
else
cout << " nie je prvocislo!" << "\n";
}
return 0;
}
Program dáva tieto výsledky:
Cislo 3 je prvocislo! Cislo 5 je prvocislo! Cislo 6 nie je prvocislo! Cislo 7 je prvocislo! Cislo 8 nie je prvocislo! Cislo 9 nie je prvocislo! Cislo 11 je prvocislo! Cislo 12 nie je prvocislo! Cislo 13 je prvocislo! Cislo 15 nie je prvocislo! Cislo 16 nie je prvocislo! Cislo 17 je prvocislo! Cislo 19 je prvocislo! Cislo 20 nie je prvocislo! Cislo 21 nie je prvocislo! Cislo 23 je prvocislo! Cislo 25 nie je prvocislo! Cislo 28 nie je prvocislo! Cislo 29 je prvocislo! Cislo 31 je prvocislo! Cislo 32 nie je prvocislo!
Všimnite si jemné vyladenie programu. Z pohľadu algoritmu je najťažšie odlíšiť tie čísla, ktoré majú ako svojho jediného deliteľa vlastnú odmocninu. Preto v podmienke dáme i > sqrt(cislo), aby sme sa vyhli falošnému priradeniu napr. čísla 25 k prvočíslam.
V budúcom dieli sa môžete tešiť na dôležitú a často vyhľadávanú tému, pointery.