CIS 3020 Part 6

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(x-1); } }

public void count2(int x) { if (X <= 0) { System.out.println(x); } else { count2(x-1); 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)	count1 has no deferred operations -- when the recursive call is completed, no further calculations must be done. This is tail recursive and an interative process. Some languages will optimize its implementation eliminating the recursion. count2 has a deferred operation -- the print operation is deferred until after the recursive call. This is a recursive process and cannot be optimized. Note that both are implemented using recursion.

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

1. Identify a pattern
2. Extract the recursive steps
3. 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ⁿ where b and n are both positive integers
• Analysis:
  • Inputs: b and n
  • Outputs: bⁿ
  • Constraints: positive integers
  • Assumptions: none
  • Relationships: none
• Design:
  • If n <= 0, then result is 1
  • if n > 0, then result is b x b^(n-1)
• Implementation:

public int expt (int b, int n) {
  int result;
  if (n<=0) {
    result = 1;
  } else {
    result = b*expt(b, n-1);
  }
  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^(n-1), do the computation in the other direction: b^(n-1) x b.
• Analysis:
  • Inputs: b, n
  • Outputs: bⁿ
  • 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¹⁶. 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, n-1);
  }
  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:

1. Move n-1 disks from pole 1 to pole 2
2. Move the n^th disk from pole 1 to pole 3
3. Move the n-1 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 n-1 disks from pole one to pole two
  • Move the n^th disk from pole one to pole three
  • Move the n-1 disks from pole two to pole three

int hanoiCount(int n) {
  int result;
  if (n==1) {
    result = 1;
  } else {
    result = hanoiCount(n-1) + 1 + hanoiCount(n-1);
  }
  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 n-1 disks from pole one to pole two
  • Move the n^th disk from pole one to pole three
  • Move the n-1 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(n-1,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 CIS 3020 Part 7