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