Laboratory 7
Chapter 18: Recursion
Before the lab, do the Self-Review exercises in the chapter.
Put the Java source code of your solution to the exercise below on your private GitHub repository:
Feel free to talk to whomever you like about any aspect of the laboratory. Working in pairs may be helpful.
Chapter 18
Do exercise 18.11 (greatest Common Divisor). After you implement that, design and implement an instrumented version, where you maintain a representation of the call stack, & print it out both before & after making recursive calls, as well as when a base case is encountered. Implement your stack with the java LinkedList class, using its push & pop methods. Store java.awt.Point objects on the stack, which is a convenient way to store the 2 argument values of the gcd algorithm. In your instrumented version, pass the stack as a 3rd argument. At the top level, invoke the instrumented gcd with 2 integer arguments and a stack with 1 entry whose value is a Point object of the integer arguments.
Using a main method, test your instrumented gcd algorithm with the following arguments:
- 5, 25
- 14, 16
- 42, 70
- -42, -70
- 1024 * 3, 512 * 5
Your output should look something like the following:
Level 0 arguments: 25 5 Pushing ... Level 0 arguments: 25 5 Level 1 arguments: 5 0 Base case encountered ... Level 0 arguments: 25 5 Level 1 arguments: 5 0 Popping ... Level 0 arguments: 25 5 gcd( 25, 5 ): 5 Level 0 arguments: 16 14 Pushing ... Level 0 arguments: 16 14 Level 1 arguments: 14 2 Pushing ... Level 0 arguments: 16 14 Level 1 arguments: 14 2 Level 2 arguments: 2 0 Base case encountered ... Level 0 arguments: 16 14 Level 1 arguments: 14 2 Level 2 arguments: 2 0 Popping ... Level 0 arguments: 16 14 Level 1 arguments: 14 2 Popping ... Level 0 arguments: 16 14 gcd( 16, 14 ): 2 Level 0 arguments: 70 42 Pushing ... Level 0 arguments: 70 42 Level 1 arguments: 42 28 Pushing ... Level 0 arguments: 70 42 Level 1 arguments: 42 28 Level 2 arguments: 28 14 Pushing ... Level 0 arguments: 70 42 Level 1 arguments: 42 28 Level 2 arguments: 28 14 Level 3 arguments: 14 0 Base case encountered ... Level 0 arguments: 70 42 Level 1 arguments: 42 28 Level 2 arguments: 28 14 Level 3 arguments: 14 0 Popping ... Level 0 arguments: 70 42 Level 1 arguments: 42 28 Level 2 arguments: 28 14 Popping ... Level 0 arguments: 70 42 Level 1 arguments: 42 28 Popping ... Level 0 arguments: 70 42 gcd( 70, 42 ): 14 Level 0 arguments: -42 -70 Pushing ... Level 0 arguments: -42 -70 Level 1 arguments: -70 -42 Pushing ... Level 0 arguments: -42 -70 Level 1 arguments: -70 -42 Level 2 arguments: -42 -28 Pushing ... Level 0 arguments: -42 -70 Level 1 arguments: -70 -42 Level 2 arguments: -42 -28 Level 3 arguments: -28 -14 Pushing ... Level 0 arguments: -42 -70 Level 1 arguments: -70 -42 Level 2 arguments: -42 -28 Level 3 arguments: -28 -14 Level 4 arguments: -14 0 Base case encountered ... Level 0 arguments: -42 -70 Level 1 arguments: -70 -42 Level 2 arguments: -42 -28 Level 3 arguments: -28 -14 Level 4 arguments: -14 0 Popping ... Level 0 arguments: -42 -70 Level 1 arguments: -70 -42 Level 2 arguments: -42 -28 Level 3 arguments: -28 -14 Popping ... Level 0 arguments: -42 -70 Level 1 arguments: -70 -42 Level 2 arguments: -42 -28 Popping ... Level 0 arguments: -42 -70 Level 1 arguments: -70 -42 Popping ... Level 0 arguments: -42 -70 gcd( -42, -70 ): -14 Level 0 arguments: 3072 2560 Pushing ... Level 0 arguments: 3072 2560 Level 1 arguments: 2560 512 Pushing ... Level 0 arguments: 3072 2560 Level 1 arguments: 2560 512 Level 2 arguments: 512 0 Base case encountered ... Level 0 arguments: 3072 2560 Level 1 arguments: 2560 512 Level 2 arguments: 512 0 Popping ... Level 0 arguments: 3072 2560 Level 1 arguments: 2560 512 Popping ... Level 0 arguments: 3072 2560 gcd( 1024*3, 512*5 ): 512