SW: Rekurzia a prevod rekurzie na iteraciu

Rekurzia je metoda zapisu algoritmu, kde sa rovnaky postup opakuje na casti vstupnych dat.

Teoreticka informatika dokazala, ze

• kazdu funkciu, ktora moze byt implementovana na von Neumannovskom pocitaci, je mozne vyjadrit rekurzivne bez pouzitia iteracie 
• kazda rekurzivna funkcia sa da vyjadrit iterativne s pouzitim zasobnika  

Vyhody reukrzie su uspornost zapisu, prirodzenost, intuitivnost a expresivnost. Uspornost a prirodzenost je asi jasna. Intuitivna preto, ze explicitne pomenuvava to, co sa opakuje v mensom. A expresivna preto, ze rekurzivne specifikacie umoznuju jednoduchu analyzu zlozitosti a overenie spravnosti. Na druhu stranu, rekurzia vyzaduje ukladanie dat na systemovy zasobnik a preto viac zatazuje systemovu pamat. Dynamicka alokacia zasobniku a ukladanie parametrov na neho predstavuje naviac casovu reziu. 

Rekurziu mozme delit na

• koncovu volanie rekurzie je poslednym prikazom algoritmu, po ktorom sa uz nevykonavaju ziadne dalsie operacie
  tato rekurzia je lahko nahraditelna iteraciou
  Prikladom je najvacsi spolocny delitel, GCD(n,m) = {n if m  = 0 | GCD(n, zvysok(n,m)) if m > 0}
   
• linearnuv tele algoritmu je len jedno rekurzivne volanie. Ak ich je viac, tak sa nachadzaju v disjunktnych vetvach programu a nikdy sa nevykonaju sucasne. Strom linearnej rekurzie je linearny.
  Faktorial, FCK(n) = {0 if n = 1 | n*FCK(n-1) if n > 1}
  
• kaskadnuv tele algoritmu su vedla seba aspon dve rekurzivne volania a strom rek. volani je teda viac-arny
  Fibonnaciho cisla, FB(n) = {1 if n = 1,2 | FB(n-1) + FB(n-2) if n > 2 }
  MergeSort, QuickSort
  
• vnorenurekurzivne funkcie, ktorych argumenty su specifikovane rekurzivne
  Ackermannova funkcia, A(m,n) = {n+1 if m = 0 | A(m-1,1) if m > 0 and n = 0 | A(m-1, A(m,n-1) if m>0 and n > 0)}
• Ackermannova funkcia je sialene rychlo rastuca funkcia, jej inverzia je zase super pomaly klesajuca. Sialene rychlo sa mysli, tak sialene, ze uz A(4,2) je super velke :). 
• http://cs.wikipedia.org/wiki/Ackermannova_funkce

Ukladanie na zasobnik sposobuje, ze rekurzivny algoritmus ma skrytu pamatovu narocnost umernu hlbke stromu, rekurzivnych volani. 

V pripade pouzitia iteracie namiesto rekurzie musime nahradit systemovy zasobnik explicitnym zasobnikom a tam je na nas, ako si to zariadime. 

Prevod na iteraciu sa da spravit v pripade kazdej rekurzivnej funkcie

RekurzivnaFcia(k) {                          NerekurzivnaFcia(k)  {
  InaFcia(k)                                           for(int i = k; i >= 0; i--)
  if(k > 0)                                                   InaFcia(i)     

      RekurzivnaFcia(k-1)                     }
}
Faktorial(n) {                                    NerekFaktorial(n)  {

  if(n > 1)                                             if (n <= 1) 

    return n*Faktorial(n-1)                     return 1

  return 1                                             int result = 1;   

}                                                            for (int i = 2; i <= n; i++) {
                                                               result = result*i;

                                                             }

                                                           }

Pri pisani rekurzie nesmieme zabudnut test na koncoby stav a osetrit hranicne podmienky. Napriklad v priklade pre faktorial sme neosetrili cisla mensie ako 0, teda osetrili, ale nespravne. Faktorial(-1) nie je 1;