kodovi/simulacija-rekurzije/Fib.java

   1 public class Fib {
   2
   3         /**
   4          * Originalna funkcija koja će biti simulirana
   5          */
   6         static int fibR(int n) {
   7                 if (n <= 1)
   8                         return n;
   9                 else
  10                         return fibR(n - 1) + fibR(n - 2);
  11         }
  12
  13         private static class InfoTip {
  14                 int n, prviSab, adr;
  15         }
  16
  17         /**
  18          * Simulirana verzija rekurzivne funkcije
  19          */
  20         static int fibS(int n) {
  21                 int prviSab, rez;
  22                 InfoTip el;
  23                 Stek<InfoTip> s = new Stek<InfoTip>(100);
  24
  25                 do {
  26                         // rekurzivni spust
  27                         while (n > 1) {
  28                                 el = new InfoTip();
  29                                 el.n = n;
  30                                 el.adr = 1;
  31                                 s.stavi(el);
  32                                 n = n - 1;
  33                         }
  34
  35                         // trivijalni slucaj
  36                         rez = n;
  37
  38                         // povratak iz rekurzije
  39                         boolean nemaPoziva = true;
  40                         while (!s.jePrazan() && nemaPoziva) {
  41                                 el = s.skiniVrh();
  42                                 n = el.n;
  43                                 if (el.adr == 1) {
  44                                         prviSab = rez;
  45                                         el.n = n;
  46                                         el.adr = 2;
  47                                         el.prviSab = prviSab;
  48                                         s.stavi(el);
  49                                         n = n - 2;
  50                                         nemaPoziva = false;
  51                                 } else {
  52                                         prviSab = el.prviSab;
  53                                         rez = prviSab + rez;
  54                                 }
  55                         }
  56
  57                 } while (!s.jePrazan());
  58                 return rez;
  59         }
  60
  61         public static void main(String[] args) {
  62                 int n = Svetovid.in.readInt("n = ?");
  63                 System.out.print("F(n) = ");
  64                 System.out.print(fibR(n));
  65                 System.out.print(" = ");
  66                 System.out.println(fibS(n));
  67         }
  68 }