Difference between revisions of "CIS 3020 Part 6"

From In The Wings
Jump to navigation Jump to search
Line 93: Line 93:
  
 
Once you have analyzed the problem, you code it as follows:
 
Once you have analyzed the problem, you code it as follows:
 +
{|
 +
|-
 
<pre>
 
<pre>
 
public returnType name(args) {
 
public returnType name(args) {
Line 103: Line 105:
 
}
 
}
 
</pre>
 
</pre>
 +
|}

Revision as of 11:21, 13 April 2007

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);
}