<![CDATA[
// Gary Yngve
// 10/1/2005
public class RecursionDemo {
// procedural style (no object instantiation), so all public static methods
public static int loop_sum(int n) {
int sum = 0;
for(int i = 1; i <= n; i++)
sum += i;
return sum;
}
public static int aug_sum(int n) {
if (n == 0) return 0; // base step
return n + aug_sum(n-1); // recursive step
}
// this idiom is a master method calling a helper method
public static int tail_sum(int n) {
return tail_sum(n,0);
}
// no naming conflict because of different signatures
private static int tail_sum(int n, int result) {
if (n == 0) return result;
return tail_sum(n-1, n+result);
}
/*
Some languages / compilers are able to convert tail-recursive
code into iterative loops. Java doesn't, but by writing the code
tail-recursively, you can see how to do the conversion yourself:
int result = 0;
int i = n;
while (i != 0) {
result += i;
i--;
}
*/
public static void main(String[] args) { // args is for command-line args
int n = 5000; // was Stack Overflowing for me at n == 10000,
// Your mileage may vary.
// Stack Overflows can also be because of
// infinite recursion due to a bug/error.
long t1 = System.currentTimeMillis();
int sum1 = aug_sum(n);
long t2 = System.currentTimeMillis(); // 1234 means 1 sec, 234 ms
int sum2 = tail_sum(n);
long t3 = System.currentTimeMillis();
int sum3 = loop_sum(n);
long t4 = System.currentTimeMillis();
// parentheses needed so it doesn't default to ("time: " + t2) - t1)
System.out.println("aug: " + sum1 + "time: " + (t2 - t1));
System.out.println("tail: " + sum2 + "time: " + (t3 - t2));
System.out.println("loop: " + sum3 + "time: " + (t4 - t3));
// Darn, they run too fast! They all finish in under a millisecond.
}
}
]]>