I started experimenting with Dart. Obviously, one of the first question is: Does it implements tail recursion?
int recursive(int n) {
if (n <= 0) return 0;
return recursive(n-1) + 1;
}
int tailRecursive (int n, int acc) {
if (n <= 1) return 0;
return tailRecursive (n-1, acc+1);
}
main() {
int max = 1000000;
double totalTime = 0.0;
for (int i = 0; i < max; i++) {
var start = Clock.now();
recursive(100);
var end = Clock.now();
totalTime += (end - start);
}
totalTime /= max;
print ('${(totalTime/Clock.frequency()) * 1000} ms');
totalTime = 0.0;
for (int i = 0; i < max; i++) {
var start = Clock.now();
tailRecursive (100,0);
var end = Clock.now();
totalTime += (end - start);
}
totalTime /= max;
print ('${(totalTime/Clock.frequency()) * 1000} ms');
}
if (n <= 0) return 0;
return recursive(n-1) + 1;
}
int tailRecursive (int n, int acc) {
if (n <= 1) return 0;
return tailRecursive (n-1, acc+1);
}
main() {
int max = 1000000;
double totalTime = 0.0;
for (int i = 0; i < max; i++) {
var start = Clock.now();
recursive(100);
var end = Clock.now();
totalTime += (end - start);
}
totalTime /= max;
print ('${(totalTime/Clock.frequency()) * 1000} ms');
totalTime = 0.0;
for (int i = 0; i < max; i++) {
var start = Clock.now();
tailRecursive (100,0);
var end = Clock.now();
totalTime += (end - start);
}
totalTime /= max;
print ('${(totalTime/Clock.frequency()) * 1000} ms');
}
Well… It seems not.
0.004474 ms
0.004762 ms
0.004762 ms
My previous post didn’t compare comparable algorithms. Because time complexity was not the same. Sorry for the confusion. First algorithm ran in O(1.618^n) and the other in O(n). Therefore, not comparable in any way! 5 minutes experiments before leaving the office are always bad…