001package algs11;
002
003import stdlib.StdDraw;
004import stdlib.StdOut;
005import stdlib.StdRandom;
006import stdlib.Trace;
007
008import java.util.Arrays;
009
010/**
011 * This is a skeleton file for your homework. Edit the sections marked TODO. You
012 * may add new functions. You may also edit the function "main" to test your
013 * code.
014 *
015 * You must not add static variables. You MAY add static functions, just not
016 * static variables.
017 *
018 * It is okay to add functions, such as
019 *
020 * <pre>
021 *     public static double sumHelper (double[] list, int i, double sumSoFar) {
022 * </pre>
023 *
024 * but it is NOT okay to add static variables, such as
025 *
026 * <pre>
027 * public static int x;
028 * </pre>
029 *
030 * As for homework 1, you must not change the declaration of any method.
031 * 
032 * You can edit the main function all you want. I will not run your main
033 * function when grading.
034 */
035public class MyRecursion {
036
037        /**
038         * As a model, here is a minValue function, both iteratively and recursively
039         */
040        /** iterative version */
041        public static double minValueI (double[] list) {
042                double result = list[0];
043                int i = 1;
044                while (i < list.length) {
045                        if (list[i] < result) result = list[i];
046                        i = i + 1;
047                }
048                return result;
049        }
050
051        /** recursive version */
052        public static double minValue (double[] list) {
053                return minValueHelper (list, 1, list[0]);
054        }
055        private static double minValueHelper (double[] list, int i, double result) {
056                if (i < list.length) {
057                        if (list[i] < result) result = list[i];
058                        result = minValueHelper (list, i + 1, result);
059                }
060                return result;
061        }
062
063        /**
064         * PROBLEM 1: Translate the following sum function from iterative to
065         * recursive.
066         *
067         * You should write a helper method. You may not use any "fields" to solve
068         * this problem (a field is a variable that is declared "outside" of the
069         * function declaration --- either before or after).
070         */
071        public static double sumI (double[] a) {
072                double result = 0.0;
073                int i = 0;
074                while (i < a.length) {
075                        result = result + a[i];
076                        i = i + 1;
077                }
078                return result;
079        }
080        public static double sum (double[] a) {
081                // TODO
082                return StdRandom.uniform ();
083        }
084
085        /**
086         * PROBLEM 2: Do the same translation for this in-place reverse function
087         *
088         * You should write a helper method. You may not use any "fields" to solve
089         * this problem (a field is a variable that is declared "outside" of the
090         * function declaration --- either before or after).
091         */
092        public static void reverseI (double[] a) {
093                int hi = a.length - 1;
094                int lo = 0;
095                while (lo < hi) {
096                        double loVal = a[lo];
097                        double hiVal = a[hi];
098                        a[hi] = loVal;
099                        a[lo] = hiVal;
100                        lo = lo + 1;
101                        hi = hi - 1;
102                }
103        }
104        public static void reverse (double[] a) {
105                // TODO
106        }
107
108        /**
109         * PROBLEM 3: The following function draws mickey mouse, if you call it like
110         * this from main:
111         *
112         * <pre>
113         * draw (.5, .5, .25);
114         * </pre>
115         *
116         * Change the code to draw mickey moose instead. Your solution should be
117         * recursive.
118         * 
119         * Before picture:
120         * http://reed.cs.depaul.edu/efredericks/ds1/images/MickeyMouse.png After picture:
121         * http://reed.cs.depaul.edu/efredericks/ds1/images/MickeyMoose.png
122         *
123         * You may not use any "fields" to solve this problem (a field is a variable
124         * that is declared "outside" of the function declaration --- either before
125         * or after).
126         */
127        public static void draw (double centerX, double centerY, double radius) {
128                // TODO 
129                if (radius < .0005) return;
130
131                StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
132                StdDraw.filledCircle (centerX, centerY, radius);
133                StdDraw.setPenColor (StdDraw.BLACK);
134                StdDraw.circle (centerX, centerY, radius);
135
136                double change = radius * 0.90;
137
138                StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
139                StdDraw.filledCircle (centerX + change, centerY + change, radius / 2);
140                StdDraw.setPenColor (StdDraw.BLACK);
141                StdDraw.circle (centerX + change, centerY + change, radius / 2);
142
143                StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
144                StdDraw.filledCircle (centerX - change, centerY + change, radius / 2);
145                StdDraw.setPenColor (StdDraw.BLACK);
146                StdDraw.circle (centerX - change, centerY + change, radius / 2);
147        }
148
149        /**
150         * PROBLEM 4: Run runTerribleLoop for one hour. You can stop the program
151         * using the red "stop" square in eclipse. Fill in the OUTPUT line below
152         * with the numbers you saw LAST --- edit the line, replacing the two ...
153         * with what you saw:
154         *
155         * OUTPUT: terribleFibonacci(...)=... // TODO
156         *
157         * Comment: the code uses "long" variables, which are like "int", but
158         * bigger. It's because fibonacci numbers get really big really fast.
159         */
160        public static void runTerribleLoop () {
161                for (int N = 0; N < 100; N++)
162                        StdOut.format ("terribleFibonacci(%2d)=%d\n", N, terribleFibonacci (N));
163        }
164        public static long terribleFibonacci (int n) {
165                if (n <= 1) return n;
166                return terribleFibonacci (n - 1) + terribleFibonacci (n - 2);
167        }
168
169        /**
170         * PROBLEM 5: The implementation of terribleFibonacci is TERRIBLE! Write a
171         * more efficient version of fibonacci. Do not change runFibonacciLoop or
172         * runFibonacciSomeValues.
173         *
174         * To make fibonacci run faster, you want it so that each call to
175         * fibonacci(n) computes the fibonacci numbers between 0 and n once, not
176         * over and over again.
177         *
178         * Comment: You will want to use a local variable of type "long" rather than
179         * type "int", for the reasons discussed above.
180         *
181         * Comment: At some point, your fibonacci numbers might become negative.
182         * This is normal and expected.
183         * http://en.wikipedia.org/wiki/Integer_overflow We discuss this at length
184         * in our systems classes.
185         *
186         * You may not use any "fields" to solve this problem (a field is a variable
187         * that is declared "outside" of the function declaration --- either before
188         * or after).
189         * 
190         * You may use a loop on this problem.
191         * You do not need to use recursion.
192         */
193        public static void runFibonacciLoop () {
194                for (int N = 0; N < 100; N++)
195                        StdOut.format ("fibonacci(%2d)=%d\n", N, fibonacci (N));
196        }
197        public static long fibonacci (int n) {
198                return 0; // TODO
199        }
200
201        /**
202         * A test program, using private helper functions.  See below.
203         * To make typing tests a little easier, I've written a function to convert strings to arrays.  See below.
204         * You can modify this -- it is not graded.
205         */
206        public static void main (String[] args) {
207                testSum ("11 21 81 -41 51 61");
208                testSum ("11 21 81 -41 51");
209                testSum ("11 21 81 -41");
210                testSum ("11 21 81");
211                testSum ("11 21");
212                testSum ("11");
213                testSum ("");
214
215                testReverse ("11 21 81 -41 51 61");
216                testReverse ("11 21 81 -41 51");
217                testReverse ("11 21 81 -41");
218                testReverse ("11 21 81");
219                testReverse ("11 21");
220                testReverse ("11");
221                testReverse ("");
222
223                testFibonacci (0, 0);
224                testFibonacci (1, 1);
225                testFibonacci (1, 2);
226                testFibonacci (2, 3);
227                testFibonacci (21, 8);
228                testFibonacci (233, 13);
229                testFibonacci (75025, 25);
230                testFibonacci (             1_836_311_903L, 46);
231                testFibonacci (             2_971_215_073L, 47);
232                testFibonacci (       308_061_521_170_129L, 71); 
233                testFibonacci (       498_454_011_879_264L, 72);
234                testFibonacci ( 7_540_113_804_746_346_429L, 92);
235                testFibonacci (-6_246_583_658_587_674_878L, 93);
236                testFibonacci (  -813_251_414_217_914_645L, 376);
237                StdOut.println ("Finished tests");
238
239                draw (.5, .5, .25);
240
241                // TODO: uncomment these temporarily when you want to see the output of your Fibonacci functions
242                //runTerribleLoop ();   
243                //runFibonacciLoop();           
244        }
245        
246        /*
247         * A main function for debugging -- change the name to "main" to run it (and
248         * rename the existing main method to something else). Change the test as
249         * appropriate.
250         */
251        public static void main1 (String[] args) {
252                Trace.drawStepsOfMethod ("minValueI");
253                Trace.drawStepsOfMethod ("minValue");
254                Trace.drawStepsOfMethod ("minValueHelper");
255                Trace.run ();
256                testMinValue ("11 21 9 31 41");
257        }
258
259        /* Test functions --- lot's of similar code! */
260        private static void testSum (String list) {
261                double[] aList = doublesFromString (list);
262                double expected = sumI (aList);
263                double actual = sum (aList);
264                if (! Arrays.equals (aList, doublesFromString (list))) {
265                        StdOut.format ("Failed sum([%s]): Array modified\n", list);
266                }
267                if (expected != actual) {
268                        StdOut.format ("Failed sum([%s]): Expecting (%.1f) Actual (%.1f)\n", list, expected, actual);
269                }
270        }
271        private static void testMinValue (String list) {
272                double[] aList = doublesFromString (list);
273                double expected = minValueI (aList);
274                double actual = minValue (aList);
275                if (! Arrays.equals (aList, doublesFromString (list))) {
276                        StdOut.format ("Failed minValue([%s]): Array modified\n", list);
277                }
278                if (expected != actual) {
279                        StdOut.format ("Failed minValue([%s]): Expecting (%.1f) Actual (%.1f)\n", list, expected, actual);
280                }
281        }
282        private static void testReverse (String list) {
283                double[] expected = doublesFromString (list);
284                reverseI (expected);
285                double[] actual = doublesFromString (list);
286                reverse (actual);
287                // != does not do what we want on arrays
288                if (! Arrays.equals (expected, actual)) {
289                        StdOut.format ("Failed reverse([%s]): Expecting (%s) Actual (%s)\n", list, Arrays.toString (expected), Arrays.toString (actual));
290                }
291        }
292        private static void testFibonacci (long expected, int n) {
293                long actual = fibonacci (n);
294                if (expected != actual) {
295                        StdOut.format ("Failed fibonacci(%d): Expecting (%d) Actual (%d)\n", n, expected, actual);
296                }
297        }
298
299        /* A utility function to create an array of doubles from a string. */
300        // The string should include a list of numbers, separated by single spaces.
301        private static double[] doublesFromString (String s) {
302                if ("".equals (s)) return new double [0]; // empty array is a special case
303                String[] nums = s.split (" ");
304                double[] result = new double[nums.length];
305                for (int i = nums.length-1; i >= 0; i--) {
306                        try { 
307                                result[i] = Double.parseDouble (nums[i]); 
308                        } catch (NumberFormatException e) { 
309                                throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
310                        }
311                }
312                return result;
313        }
314}