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.