kodovi/simulacija-rekurzije/Rek2.java

   1 /**
   2  * Kompleksniji primer u kome simuliramo funkciju cije funkcionisanje
   3  * i rezultat nisu nuzno jasni.
   4  *
   5  * U funkciji postoje ugnjezdjeni pozivi na koje treba obratiti paznju.
   6  *
   7  * Ova verzija resenja takodje sadrzi i ispise parametara na 'ulazu' u
   8  * funkciju, i iste takve kod simulirane verzije da se jasno vidi da se
   9  * svi pozivi desavaju u istom redosledu, pri cemu su dodatno naznacene
  10  * adrese poziva u simuliranoj verziji. Ovakav dodatak nije potreban inace
  11  * za resavanje, ali moze pomoci u razumevanju i proveri da li je
  12  * sve ispravno uradjeno.
  13  */
  14 public class Rek2 {
  15
  16         static int g(int x, int y, int n) {
  17                 System.out.printf("0 %d %d %d\n",x,y,n);
  18                 if (n < 3) {
  19                         return x + y;
  20                 }
  21
  22                 if (n % 2 == 1) {
  23                         return g(g(x + 1, y, n - 2), y, n - 3);
  24                 } else {
  25                         return g(x, g(x, y + 1, n - 2), n - 3);
  26                 }
  27         }
  28
  29         private static class InfoTip {
  30                 int x, y, n, adr;
  31         }
  32
  33         static int gS(int x, int y, int n) {
  34                 int rez;
  35                 InfoTip el;
  36                 Stek<InfoTip> s = new Stek<InfoTip>();
  37                 System.out.printf("%d %d %d %d\n",0,x,y,n);
  38
  39                 do {
  40                         // rekurzivni spust
  41                         while (n >= 3) {
  42                                 if (n % 2 == 1) {
  43                                         el = new InfoTip();
  44                                         el.x = x;
  45                                         el.y = y;
  46                                         el.n = n;
  47                                         el.adr = 1;
  48                                         s.stavi(el);
  49                                         x = x + 1;
  50                                         n = n - 2;
  51                                         System.out.printf("%d %d %d %d\n",el.adr,x,y,n);
  52                                 } else {
  53                                         el = new InfoTip();
  54                                         el.x = x;
  55                                         el.y = y;
  56                                         el.n = n;
  57                                         el.adr = 3;
  58                                         s.stavi(el);
  59                                         y = y + 1;
  60                                         n = n - 2;
  61                                         System.out.printf("%d %d %d %d\n",el.adr,x,y,n);
  62                                 }
  63                         }
  64
  65                         // trivijalni slucaj
  66                         rez = x + y;
  67
  68                         // povratak iz rekurzije
  69                         boolean nemaPoziva = true;
  70                         while (!s.jePrazan() && nemaPoziva) {
  71                                 el = s.skiniVrh();
  72                                 x = el.x;
  73                                 y = el.y;
  74                                 n = el.n;
  75                                 if (el.adr == 1) {
  76                                         el.x = x; // nije potrebno zapravo
  77                                         el.y = y; // nije potrebno zapravo
  78                                         el.n = n; // nije potrebno zapravo
  79                                         el.adr = 2;
  80                                         s.stavi(el);
  81                                         x = rez;
  82                                         n = n - 3;
  83                                         System.out.printf("%d %d %d %d\n",el.adr,x,y,n);
  84                                         nemaPoziva = false;
  85                                 } else if (el.adr == 3) {
  86                                         el.x = x; // nije potrebno zapravo
  87                                         el.y = y; // nije potrebno zapravo
  88                                         el.n = n; // nije potrebno zapravo
  89                                         el.adr = 4;
  90                                         s.stavi(el);
  91                                         y = rez;
  92                                         n = n - 3;
  93                                         System.out.printf("%d %d %d %d\n",el.adr,x,y,n);
  94                                         nemaPoziva = false;
  95                                 } // adr 2 i 4
  96                                   // rez = rez; nema smisla pisati
  97                         }
  98                 } while (!s.jePrazan());
  99                 return rez;
 100         }
 101
 102         public static void main(String[] args) {
 103                 System.out.println(g(2, 3, 11));
 104                 System.out.println(gS(2, 3, 11));
 105         }
 106 }