The following code with run keys "-ea -Xmx256m -Xss64m" gives on my computer (Core2Duo 1.83Ghz, L2 cache 2Mb, ram 2Gb) this output:
1.751140997 sec
0.216811633 sec
Recursion works extremely slow. What's wrong with it?
public class DoYouWantToSeeSomeMagic {
static class List {
List next;
public List(List next) {
this.next = next;
}
}
private static List createListSlow(int n) {
if (n == 0) {
return new List(null);
} else {
return new List(createListSlow(n - 1));
}
}
private static List createListFast(int n) {
List[] list = new List[n + 1];
list[0] = new List(null);
for (int i = 1; i <= n; ++i) {
list[i] = new List(list[i - 1]);
}
return list[n];
}
public static void main(String[] args) {
final int N = 1 << 20;
{
long time = System.nanoTime();
createListSlow(N);
System.err.println((System.nanoTime() - time) / 1e9 + " sec");
}
{
long time = System.nanoTime();
createListFast(N);
System.err.println((System.nanoTime() - time) / 1e9 + " sec");
}
}
}
If I change N to (1 << 19) the output is:
0.129561439 sec
0.129751965 sec
