kodovi/simulacija-rekurzije/Stepenovanje.java

   1 public class Stepenovanje {
   2
   3         static double kvadrat(double y) {
   4                 return y * y;
   5         }
   6
   7         /**
   8          * Originalna funkcija koja će biti simulirana
   9          */
  10         static double naStepenR(double x, int n) {
  11                 if (n <= 0)
  12                         return 1;
  13                 else if (n % 2 != 0)
  14                         return x * kvadrat(naStepenR(x, n / 2));
  15                 else
  16                         return kvadrat(naStepenR(x, n / 2));
  17         }
  18
  19         private static class InfoTip {
  20                 double x;
  21                 int n;
  22                 int adr;
  23         }
  24
  25         /**
  26          * Simulirana verzija rekurzivne funkcije
  27          */
  28         static double naStepenS(double x, int n) {
  29                 InfoTip el;
  30                 Stek<InfoTip> s = new Stek<InfoTip>(100);
  31
  32                 // rekurzivni silaz
  33                 while (n > 0) {
  34                         if (n % 2 != 0) {
  35                                 el = new InfoTip();
  36                                 el.x = x;
  37                                 el.n = n;
  38                                 el.adr = 1;
  39                                 s.stavi(el);
  40                         } else {
  41                                 el = new InfoTip();
  42                                 el.x = x;
  43                                 el.n = n;
  44                                 el.adr = 2;
  45                                 s.stavi(el);
  46                         }
  47                         n = n / 2;
  48                 }
  49
  50                 // trivijalni slucaj
  51                 double rez = 1.0;
  52
  53                 // povratak iz rekurzije
  54                 while (!s.jePrazan()) {
  55                         el = s.skiniVrh();
  56                         x = el.x;
  57                         n = el.n;
  58                         if (el.adr == 1)
  59                                 rez = x * kvadrat(rez);
  60                         else
  61                                 rez = kvadrat(rez);
  62                 }
  63                 return rez;
  64         }
  65
  66         public static void main(String[] args) {
  67                 System.out.print("x = ");
  68                 double x = Svetovid.in.readDouble();
  69                 System.out.print("n = ");
  70                 int n = Svetovid.in.readInt();
  71                 System.out.print("x^n = ");
  72                 System.out.print(naStepenR(x, n));
  73                 System.out.print(" = ");
  74                 System.out.println(naStepenS(x, n));
  75         }
  76 }