kodovi/simulacija-rekurzije/Faktorijel.java

   1 /**
   2  * Primer veoma jednostavne rekurzivne funkcije u kojoj se pozivi linearno
   3  * spuštaju do trivijalnog uslova i potom se direktno vraćaju do originalnog
   4  * poziva. Pri tome ne postoje ni nikakve dodatne promenljive ili pozivi.
   5  */
   6 public class Faktorijel {
   7
   8         /**
   9          * Originalna funkcija koja će biti simulirana
  10          */
  11         static int faktorijelR(int n) {
  12                 if (n <= 1)
  13                         return 1;
  14                 else
  15                         return n * faktorijelR(n - 1);
  16         }
  17
  18         /**
  19          * Simulirana verzija rekurzivne funkcije, u kojoj se samo posmatra
  20          * rekurzivni spust i povratak, posto u ovoj jednostavnoj funkciji i ne
  21          * postoji nista drugo. Takodje se na steku samo cuva vrednost parametra
  22          * 'n', nije pravljen infotip jer nema potrebe.
  23          */
  24         static int faktorijelS(int n) {
  25                 Stek<Integer> s = new Stek<Integer>(100);
  26
  27                 // rekurzivni pozivi do trivijalnog slučaja
  28                 while (n > 1) {
  29                         s.stavi(n);
  30                         n--;
  31                 }
  32
  33                 // trivijalni slučaj
  34                 int rez = 1;
  35
  36                 // povratak iz rekurzije
  37                 while (!s.jePrazan()) {
  38                         n = s.skiniVrh();
  39                         rez = rez * n;
  40                 }
  41                 return rez;
  42         }
  43
  44         // eksplicitni infotip koji se uklapa u algoritam pretvaranja funkcije
  45         static private class InfoTip {
  46                 int n;
  47                 int adr; // nema potrebe kad ima samo jedan poziv
  48         }
  49
  50         /**
  51          * Simulirana verzija rekurzivne funkcije, sa svim detaljima datog algoritma
  52          * za transformaciju. Mnogi detalji su nepotrebni za ovu funkciju, sto je i
  53          * oznaceno, medjutim nije greska navesti ih
  54          */
  55         static int faktorijelSDetaljno(int n) {
  56                 Stek<InfoTip> s = new Stek<>(100);
  57                 int rez;
  58                 InfoTip el;
  59
  60                 do {
  61                         // rekurzivni pozivi do trivijalnog slučaja
  62                         while (n > 1) {
  63                                 el = new InfoTip();
  64                                 el.n = n;
  65                                 el.adr = 1;// drugo ni ne postoji
  66                                 s.stavi(el);
  67                                 n--;
  68                         }
  69
  70                         // trivijalni slučaj
  71                         rez = 1;
  72
  73                         // povratak iz rekurzije
  74                         boolean nemaPoziva = true;
  75                         while (!s.jePrazan() && nemaPoziva) {
  76                                 el = s.skiniVrh();
  77                                 n = el.n;
  78                                 if (el.adr == 1) {
  79                                         rez = rez * n;
  80                                 } // ne postoje druge adrese
  81                         }
  82
  83                         // posto se 'nemaPoziva' ne menja
  84                         // u ovom momentu ce s uvek biti prazan
  85                         // pa nema potrebe ni za ovom petljom
  86                 } while (!s.jePrazan());
  87
  88                 return rez;
  89         }
  90
  91         public static void main(String[] args) {
  92                 int n = Svetovid.in.readInt("n = ?");
  93                 System.out.print("n! = ");
  94                 System.out.print(faktorijelR(n));
  95                 System.out.print(" = ");
  96                 System.out.print(faktorijelS(n));
  97                 System.out.print(" = ");
  98                 System.out.println(faktorijelSDetaljno(n));
  99         }
 100 }