Difference between revisions of "CIS 3020 Part 6"

Revision as of 16:01, 13 April 2007

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

Executing with x=4:
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.

@@ Line 72: / Line 72: @@
 Exiting count2(4)
 </pre>
+||
+* 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.
 |}