in reply to
Adding 2 + 2

At first, I tried this simple recursive algorithm:

`#!/usr/bin/perl -w
use strict;
use warnings;
sub add {
my ($first, @rest) = @_;
if (!defined $first) {
0;
}
else {
die "operand may not be negative!" unless $first >= 0;
if ($first == 0) {
add(@rest);
}
else {
1 + add($first-1, @rest);
}
}
}
sub print_add {
print join(" + ", @_), " = ", add(@_), "\n";
}
print_add 2,2;
print_add 2,2,2;
print_add 4,8,12;
`

which yields the results:

`root@swill ~/PerlMonks
$ ./adder_1.pl
2 + 2 = 4
2 + 2 + 2 = 6
4 + 8 + 12 = 24
`

But I then realized that the algorithm used is essentially tail-recursive.

*Thus, it can be optimized!* Converting the add routine from tail-recursive form to an iterative form yields:

`sub add {
my $accumulator = 0;
for my $op (@_) {
for my $i (1 .. $op) {
$accumulator = $accumulator+1;
}
}
$accumulator;
}
`

Now all that remained is to verify that the conversion was worthwhile:

`#!/usr/bin/perl -w
use strict;
use warnings;
use Benchmark qw(timethese cmpthese);
sub add_rec {
my ($first, @rest) = @_;
if (!defined $first) {
0;
}
else {
die "operand may not be negative!" unless $first >= 0;
if ($first == 0) {
add_rec(@rest);
}
else {
1 + add_rec($first-1, @rest);
}
}
}
sub add_iter {
my $accumulator = 0;
for my $op (@_) {
for my $i (1 .. $op) {
$accumulator = $accumulator+1;
}
}
$accumulator;
}
cmpthese(100000, {
'Recursive' => sub { 2 == add_rec(2,2); },
'Iterative' => sub { 2 == add_iter(2,2); }
});
`

Running the benchmarking program shows:

`$ ./adder_bench.pl
Rate Recursive Iterative
Recursive 79051/s -- -48%
Iterative 152207/s 93% --
`

Success!

The iterative version is *much* faster than the recursive one. I'm certain that this new algorithm for adding should be used in all future programs, as the iterative version is better both in speed (*it's nearly twice as fast!*) as well as consuming far less memory than it's recursive counterpart when adding large numbers.

--roboticus

*Awaiting his Turing prize for this valuable discovery...*