Simulacija rekurzije, primeri sa prvog casa

diff --git a/kodovi/simulacija-rekurzije/Faktorijel.java b/kodovi/simulacija-rekurzije/Faktorijel.java
new file mode 100644 (file)
index 0000000..097f2b5
--- /dev/null
+++ b/kodovi/simulacija-rekurzije/Faktorijel.java
@@ -0,0 +1,48 @@
+/**\r
+ * Primer veoma jednostavne rekurzivne funkcije u kojoj se pozivi linearno\r
+ * spuštaju do trivijalnog uslova i potom se direktno vraćaju do originalnog\r
+ * poziva. Pri tome ne postoje ni nikakve dodatne promenljive ili pozivi.\r
+ */\r
+public class Faktorijel {\r
+\r
+       /**\r
+        * Originalna funkcija koja će biti simulirana\r
+        */\r
+       static int faktorijelR(int n) {\r
+               if (n <= 1)\r
+                       return 1;\r
+               else\r
+                       return n * faktorijelR(n - 1);\r
+       }\r
+\r
+       /**\r
+        * Simulirana verzija rekurzivne funkcije\r
+        */\r
+       static int faktorijelS(int n) {\r
+               Stek<Integer> s = new Stek<Integer>(100);\r
+\r
+               // rekurzivni pozivi do trivijalnog slučaja\r
+               while (n > 1) {\r
+                       s.stavi(n);\r
+                       n--;\r
+               }\r
+\r
+               // trivijalni slučaj\r
+               int rez = 1;\r
+\r
+               // povratak iz rekurzije\r
+               while (!s.jePrazan()) {\r
+                       n = s.skiniVrh();\r
+                       rez = rez * n;\r
+               }\r
+               return rez;\r
+       }\r
+\r
+       public static void main(String[] args) {\r
+               int n = Svetovid.in.readInt("n = ?");\r
+               System.out.print("n! = ");\r
+               System.out.print(faktorijelR(n));\r
+               System.out.print(" = ");\r
+               System.out.println(faktorijelS(n));\r
+       }\r
+}
\ No newline at end of file

diff --git a/kodovi/simulacija-rekurzije/Fib.java b/kodovi/simulacija-rekurzije/Fib.java
new file mode 100644 (file)
index 0000000..04a48aa
--- /dev/null
+++ b/kodovi/simulacija-rekurzije/Fib.java
@@ -0,0 +1,68 @@
+public class Fib {\r
+\r
+       /**\r
+        * Originalna funkcija koja će biti simulirana\r
+        */\r
+       static int fibR(int n) {\r
+               if (n <= 1)\r
+                       return n;\r
+               else\r
+                       return fibR(n - 1) + fibR(n - 2);\r
+       }\r
+\r
+       private static class InfoTip {\r
+               int n, prviSab, adr;\r
+       }\r
+\r
+       /**\r
+        * Simulirana verzija rekurzivne funkcije\r
+        */\r
+       static int fibS(int n) {\r
+               int prviSab, rez;\r
+               InfoTip el;\r
+               Stek<InfoTip> s = new Stek<InfoTip>(100);\r
+               \r
+               do {\r
+                       // rekurzivni spust\r
+                       while (n > 1) {\r
+                               el = new InfoTip();\r
+                               el.n = n;\r
+                               el.adr = 1;\r
+                               s.stavi(el);\r
+                               n = n - 1;\r
+                       }\r
+                       \r
+                       // trivijalni slucaj\r
+                       rez = n;\r
+                       \r
+                       // povratak iz rekurzije\r
+                       boolean nemaPoziva = true;\r
+                       while (!s.jePrazan() && nemaPoziva) {\r
+                               el = s.skiniVrh();\r
+                               n = el.n;\r
+                               if (el.adr == 1) {\r
+                                       prviSab = rez;\r
+                                       el.n = n;\r
+                                       el.adr = 2;\r
+                                       el.prviSab = prviSab;\r
+                                       s.stavi(el);\r
+                                       n = n - 2;\r
+                                       nemaPoziva = false;\r
+                               } else {\r
+                                       prviSab = el.prviSab;\r
+                                       rez = prviSab + rez;\r
+                               }\r
+                       }\r
+                       \r
+               } while (!s.jePrazan());\r
+               return rez;\r
+       }\r
+\r
+       public static void main(String[] args) {\r
+               int n = Svetovid.in.readInt("n = ?");\r
+               System.out.print("F(n) = ");\r
+               System.out.print(fibR(n));\r
+               System.out.print(" = ");\r
+               System.out.println(fibS(n));\r
+       }\r
+}
\ No newline at end of file

diff --git a/kodovi/simulacija-rekurzije/Stek.java b/kodovi/simulacija-rekurzije/Stek.java
new file mode 100644 (file)
index 0000000..a3e07c9
--- /dev/null
+++ b/kodovi/simulacija-rekurzije/Stek.java
@@ -0,0 +1,143 @@
+/**\r
+ * Tip podataka stek, koji omogućava skladištenje podataka u skladu sa principom\r
+ * "poslednji unutra, prvi napolje".\r
+ * \r
+ * <p>\r
+ * Implementacija koristi niz, te je u skladu sa tim ograničena veličina steka\r
+ * koji se koristi i moguće je da će operacija za dodavanje elemenata baciti\r
+ * izuzetak ukoliko nema mesta.\r
+ * </p>\r
+ * \r
+ * @version v1.0.0\r
+ * \r
+ * @param <T>\r
+ *            Tip podataka koji će se čuvati u konkretnoj instanci steka.\r
+ */\r
+public class Stek<T> {\r
+       /**\r
+        * Separator vrednosti u {@code toString} metodu: {@value} .\r
+        */\r
+       public static final String SEPARATOR = ", ";\r
+\r
+       // indeks prvog slobodnog elementa na steku\r
+       private int popunjeno;\r
+\r
+       // niz u kome se skladiste elementi\r
+       private T[] elementi;\r
+\r
+       /**\r
+        * Veličina stekova za koje nije prosledjen parametar o veličini ({@value}\r
+        * ).\r
+        */\r
+       public static final int PODRAZUMEVANA_VELICINA = 100;\r
+\r
+       /**\r
+        * Kreira novi Stek podrazumevane veličine {@value #PODRAZUMEVANA_VELICINA}.\r
+        */\r
+       public Stek() {\r
+               this(PODRAZUMEVANA_VELICINA);\r
+       }\r
+\r
+       /**\r
+        * Kreira nov Stek zadate velicine.\r
+        * \r
+        * @param n\r
+        *            maksimalan broj elemenata koji će ovaj stek moći da primi.\r
+        */\r
+       // pozeljno koristiti Suppress da kompajliranje ne prijavljuje upozorenja\r
+       @SuppressWarnings("unchecked")\r
+       public Stek(int n) {\r
+               popunjeno = 0;\r
+               elementi = (T[]) (new Object[n]);\r
+       }\r
+\r
+       /**\r
+        * Vraća da li je stek prazan.\r
+        * \r
+        * @return da li je stek prazan\r
+        */\r
+       public boolean jePrazan() {\r
+               return popunjeno == 0;\r
+       }\r
+\r
+       /**\r
+        * Vraća da li je stek pun.\r
+        * \r
+        * @return da li je stek pun\r
+        */\r
+       public boolean jePun() {\r
+               return popunjeno == elementi.length;\r
+       }\r
+\r
+       /**\r
+        * Vraća vrednost elementa na vrhu steka. Ukoliko je stek prazan baca\r
+        * izuzetak.\r
+        * \r
+        * @return vrednost elementa na vrhu steka\r
+        */\r
+       public T vrh() {\r
+               if (jePrazan()) {\r
+                       throw new IllegalStateException("Stek je prazan");\r
+               } else\r
+                       return elementi[popunjeno - 1];\r
+       }\r
+\r
+       /**\r
+        * Skida element sa vrha steka i vraća ga. Ukoliko je stek prazan baca se\r
+        * izuzetak.\r
+        * \r
+        * @return vrednost elementa koji je bio na vrhu steka\r
+        */\r
+       public T skiniVrh() {\r
+               if (jePrazan()) {\r
+                       throw new IllegalStateException("Stek je prazan");\r
+               } else\r
+                       popunjeno--;\r
+               return elementi[popunjeno];\r
+       }\r
+\r
+       /**\r
+        * Ubacuje prosleđeni element na vrh steka. Ukoliko je stek već pun baca se\r
+        * izuzetak.\r
+        * \r
+        * @param x\r
+        *            element koji će biti ubačen na vrh steka\r
+        */\r
+       public void stavi(T x) {\r
+               if (jePun()) {\r
+                       throw new IllegalStateException("Stek je pun");\r
+               } else {\r
+                       elementi[popunjeno] = x;\r
+                       popunjeno++;\r
+               }\r
+       }\r
+\r
+       /**\r
+        * Vraća String reprezentaciju ovog Steka. Reprezentacija će sadržati\r
+        * najviše 4 elementa sa steka, tačnije najviše prva dva i poslednja dva,\r
+        * razdvojenih sa {@value #SEPARATOR}, a ukoliko ima više od 4 elementa biće\r
+        * dodato i "..." između prvih i poslednjih elemenata.\r
+        */\r
+       public String toString() {\r
+               String rez = "Stek: ";\r
+               if (jePrazan()) {\r
+                       rez += "prazan";\r
+               } else {\r
+                       rez += elementi[popunjeno - 1];\r
+                       if (popunjeno > 1) {\r
+                               int sledeci = popunjeno - 2;\r
+                               rez += SEPARATOR + elementi[sledeci];\r
+                               if (popunjeno > 2) {\r
+                                       if (popunjeno > 4) {\r
+                                               rez += SEPARATOR + "...";\r
+                                       }\r
+                                       if (popunjeno > 3) {\r
+                                               rez += SEPARATOR + elementi[1];\r
+                                       }\r
+                                       rez += SEPARATOR + elementi[0];\r
+                               }\r
+                       }\r
+               }\r
+               return rez;\r
+       }\r
+}
\ No newline at end of file

diff --git a/kodovi/simulacija-rekurzije/Stepenovanje.java b/kodovi/simulacija-rekurzije/Stepenovanje.java
new file mode 100644 (file)
index 0000000..7417032
--- /dev/null
+++ b/kodovi/simulacija-rekurzije/Stepenovanje.java
@@ -0,0 +1,76 @@
+public class Stepenovanje {\r
+\r
+       static double kvadrat(double y) {\r
+               return y * y;\r
+       }\r
+\r
+       /**\r
+        * Originalna funkcija koja će biti simulirana\r
+        */\r
+       static double naStepenR(double x, int n) {\r
+               if (n <= 0)\r
+                       return 1;\r
+               else if (n % 2 != 0)\r
+                       return x * kvadrat(naStepenR(x, n / 2));\r
+               else\r
+                       return kvadrat(naStepenR(x, n / 2));\r
+       }\r
+\r
+       private static class InfoTip {\r
+               double x;\r
+               int n;\r
+               int adr;\r
+       }\r
+\r
+       /**\r
+        * Simulirana verzija rekurzivne funkcije\r
+        */\r
+       static double naStepenS(double x, int n) {\r
+               InfoTip el;\r
+               Stek<InfoTip> s = new Stek<InfoTip>(100);\r
+               \r
+               // rekurzivni silaz\r
+               while (n > 0) {\r
+                       if (n % 2 != 0) {\r
+                               el = new InfoTip();\r
+                               el.x = x;\r
+                               el.n = n;\r
+                               el.adr = 1;\r
+                               s.stavi(el);\r
+                       } else {\r
+                               el = new InfoTip();\r
+                               el.x = x;\r
+                               el.n = n;\r
+                               el.adr = 2;\r
+                               s.stavi(el);\r
+                       }\r
+                       n = n / 2;\r
+               }\r
+               \r
+               // trivijalni slucaj\r
+               double rez = 1.0;\r
+               \r
+               // povratak iz rekurzije\r
+               while (!s.jePrazan()) {\r
+                       el = s.skiniVrh();\r
+                       x = el.x;\r
+                       n = el.n;\r
+                       if (el.adr == 1)\r
+                               rez = x * kvadrat(rez);\r
+                       else\r
+                               rez = kvadrat(rez);\r
+               }\r
+               return rez;\r
+       }\r
+\r
+       public static void main(String[] args) {\r
+               System.out.print("x = ");\r
+               double x = Svetovid.in.readDouble();\r
+               System.out.print("n = ");\r
+               int n = Svetovid.in.readInt();\r
+               System.out.print("x^n = ");\r
+               System.out.print(naStepenR(x, n));\r
+               System.out.print(" = ");\r
+               System.out.println(naStepenS(x, n));\r
+       }\r
+}
\ No newline at end of file