CIS 3020 Part 6
Jump to navigation
Jump to search
Ordering of Statements in Methods
Consider the following two methods:
public void count1(int x) { if (X <= 0) { System.out.println(x); } else { System.out.println(x); count1(x1); } } 
public void count2(int x) { if (X <= 0) { System.out.println(x); } else { count2(x1); System.out.println(x); } } 
 Do they calculate the same values?
 Do they do the calculations in the same way?
 Do they print the same results?
Executing with X=4
count1  count2  Analysis 

Entering count1(4) 4 Entering count1(3) 3 Entering count1(2) 2 Entering count1(1) 1 Entering count1(0) 0 Exiting count1(0) Exiting count1(1) Exiting count1(2) Exiting count1(3) Exiting count1(4) 
Entering count2(4) Entering count2(3) Entering count2(2) Entering count2(1) Entering count2(0) 0 Exiting count2(0) 1 Exiting count2(1) 2 Exiting count2(2) 3 Exiting count2(3) 4 Exiting count2(4) 

Recursion
 The key idea in recursion is:
 To solve a problem in terms of its solution
 To understand recursion, you must first understand recursion
 A recursive solution has two parts:
 Base cases: A simple easy to solve problem that terminates the recursion
 Recursive cases: A problem whose solution requires a recursive solution with a smaller (closer to the base case) problem.
Analyzing a Recursive Problem
 Identify a pattern
 Extract the recursive steps
 Extract the base cases
Once you have analyzed the problem, you code it as follows:
public returnType name(args) { if (base_case) { // base case solution } else { // recursive steps } return (return_value); } 
Exponentiation
 Suppose that we would like to compute b^{n} where b and n are both positive integers
 Analysis:
 Inputs: b and n
 Outputs: b^{n}
 Constraints: positive integers
 Assumptions: none
 Relationships: none
 Design:
 If n <= 0, then result is 1
 if n > 0, then result is b x b^{(n1)}
 Implementation:
public int expt (int b, int n) { int result; if (n<=0) { result = 1; } else { result = b*expt(b, n1); } return (result); }
Note: This is a linear recursive process
Convert to an iterative process (tail recursive)
 Note that this is not the only way that we can compute exponentiation
 Rather than compute b x b^{(n1)}, do the computation in the other direction: b^{(n1)} x b.
 Analysis:
 Inputs: b, n
 Outputs: b^{n}
 Constraints: positive and integer
 Assumptions: none
 Relationships: none
Alternative
 In this approach we keep track of the computed value (product) as we run a counter from n to 0
 Each time we decrement the counter, we multiply the product by the current value of b until the counter reaches 0
 The counter tells us if we have reached the stopping point
Design
 If counter <= 0 then
 Result is product we have been computing
 If counter is any other value
 Product is our product so far times b
 Decrement the counter
 Try again
What must our product start at? 1
What must our counter start at? n
public int expt(int b, int n) { return (doExpt(b, n, 1); } public int doExpt(int b, int count, int prod) { int result; if (count <= 0) { result = prod; } else { result = doExpt(b, count  1, b * prod); } return result; }
Doing these calculations faster
Consider the case of b^{16}. The calculations can be done in just four multiplications rather than fifteen as the preceding methods use. Implementation requires working backwards.
public int expt(int b, int n) { return (fastExpt(b,n)); } private int fastExpt(int b, int n) { int result; if (n<=0) { result = 1; } else if (even(n)) { result = square(fastExpt(b, n/2)); } else { result = b * fastExpt(b, n1); } return result; } private int square (int x) { return (x*x); } private boolean even (int x) { return (x%2 == 0); }
NOTE: Double the size of the problem (the exponent n), the number of steps only increases by 1.
 Because doubling the size of the problem (the exponent n) only causes the number of steps to increase by one, we identify the run time as logarithmic. This makes the O() of the algorithm O(log n).
Tower of Hanoi Problem
 There are 57 disks of graduated size stacked on the first pole of a set of three poles.
 Moving one disk at a time you are to move all disks from the first pole to the third pole.
 Contraint: No disk can be placed on a smaller disk.
Solution
Break the problem into a set of smaller/simpler problems:
 Move n1 disks from pole 1 to pole 2
 Move the n^{th} disk from pole 1 to pole 3
 Move the n1 disks from pole 2 to pole 3
Code to Count Moves
 If there is one disk to move, then result is one
 If there are two or more disks to move, then result is:
 Move n1 disks from pole one to pole two
 Move the n^{th} disk from pole one to pole three
 Move the n1 disks from pole two to pole three
int hanoiCount(int n) { int result; if (n==1) { result = 1; } else { result = hanoiCount(n1) + 1 + hanoiCount(n1); } return result; }
Code to track the moves
 If there is one disk to move, then move it.
 If there are two or more disks to move, then result is:
 Move n1 disks from pole one to pole two
 Move the n^{th} disk from pole one to pole three
 Move the n1 disks from pole two to pole three
void hanoiMoves(int n, int p1, int p2, int p3) { if (n==1) { println("Move from " + p1 + " to " + p3); } else { hanoiMoves(n1,p1,p3,p2); hanoiMoves(1,p1,p2,p3); hanoiMoves(p1,p2,p1,p3); } } 
n = number of disks to move p1 = pole where disks currently are p2 = temporary pole p3 = destination pole 