CIS 3020 Part 6

From In The Wings
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(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 bn where b and n are both positive integers
  • Analysis:
    • Inputs: b and n
    • Outputs: bn
    • 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: bn
    • 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;
}