přejít na obsah přejít na navigaci

Linux E X P R E S, Programovanie v jazyku C++: Rekurzívne funkcie

Symphera - PM konference

Programovanie v jazyku C++: Rekurzívne funkcie

cplusplus.png

Naučte sa využívať rekurzívne funkcie, vďaka ktorým môžete ušetriť nemálo času a kódu pri vývoji a získať benefity ako napr. zjednodušenie či spriehľadnenie programu.


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.

Nahoru

Příspěvky

Programovanie v jazyku C++: Rekurzívne funkcie
fela 30. 07. 2018, 14:08:04
Odpovědět  Odkaz 
Hmm.. pointery... to dokáže s človekom pekne zamávať ;)
Re: Programovanie v jazyku C++: Rekurzívne funkcie
Ash 31. 07. 2018, 19:39:34
Odpovědět  Odkaz 
auto_ptr už nie je súčasťou štandardu od C++11. Jeho problém bol, že sa nedal použiť v STL kontajneroch. Jeho náhradou je unique_ptr, ktorý by mal byť prednostne používaný na správu vlastníctva alokovaných objektov, pokiaľ nie je vážny dôvod použiť shared_ptr.
Re: Re: Programovanie v jazyku C++: Rekurzívne funkcie
Ash 31. 07. 2018, 19:41:24
Odpovědět  Odkaz 
Pardon, nesprávny klik.
Programovanie v jazyku C++: Rekurzívne funkcie
Jano 31. 07. 2018, 15:02:26
Odpovědět  Odkaz 
Už sa teším na pointery. Vždy som chcel vedieť ako fungujú std::unique_ptr, std::shared_ptr, std::weak_ptr a prečo je std::auto_ptr design flaw.
Re: Programovanie v jazyku C++: Rekurzívne funkcie
Ash 31. 07. 2018, 19:40:49
Odpovědět  Odkaz 
auto_ptr už nie je súčasťou štandardu od C++11. Jeho problém bol, že sa nedal použiť v STL kontajneroch. Jeho náhradou je unique_ptr, ktorý by mal byť prednostne používaný na správu vlastníctva alokovaných objektov, pokiaľ nie je vážny dôvod použiť shared_ptr.

Přidat názor

Nejsou podporovány žádné značky, komentáře jsou jen čistě textové. Více o diskuzích a pravidlech najdete v nápovědě.
Diskuzi můžete sledovat pomocí RSS kanálu rss



 
 

Top články z OpenOffice.cz

Eduard Boldižár

Eduard Boldižár

Som redaktorom stránky astrotech.cz. Mám 25 rokov. Medzi moje záľuby patrí astronómia, sci-fi literatúra a programovanie.


  • Distribuce: ubuntu
  • Grafické prostředí: unity



Public Relations

Český startup umožňuje automatické investování

PortuPortu je první online automatizovaná investiční platforma v Česku. Sestaví vám portfolio na míru a vy se nemusíte o nic starat – jen sledovat, jak vaše peníze pracují za vás.

Pokračování ...


Redakční blog

Pavel Fric

Pavel Fric, 26. leden

MuseScore 3

První aktualizace třetí řady notačního editoru MuseScore


Redakce

Redakce, 21. prosinec

Pište pro LinuxEXPRES

Baví vás Linux? Pište o něm, není to nic těžkého. LinuxEXPRES hledá nové autory.


Pavel Fric

Pavel Fric, 23. říjen

Nové motivy pro přehrávač Sayonara

Pomozte rozšířit možnost měnit vzhled programu za běhu


Všechny blogy »

eXo space