Recursion is a very common technique used in today's programs. Although recursion is a very easy method to solve problems, it can easily introduce unwanted overhead that can quickly worsen program's performance.
The facts,
1) We created a recursive function to calculate the number of nodes in a full binary tree, given as argument the tree's height.
2) We implemented this function in Parrot, and also on interpreted and compiled languges.
3) We ran the programs several times increasing the height of the tree.
Here are the results:
Re:sources?
smash on 2008-04-13T18:30:57
The sources are available in http://nrc.homelinux.org/parrot/bintree/.Re:sources?
pmichaud on 2008-04-13T18:41:10
Thanks, that helps a bunch.
Pm
Re:bintree.pl eq
ChrisDolan on 2008-04-14T02:14:43
I cleaned up n_of_nodes as follows and achieved a 20% speedup for the Perl version. Most of the speedup came from changing "eq" to "==" but interestingly using a ternary instead of an if-else helped too. That is probably because I removed a "return" statement in the process.
sub n_of_nodes {
my ($x) = @_;
return $x == 0 ? 1 : 1 + n_of_nodes($x-1) + n_of_nodes($x-1);
}
