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.