If you can arrange your algorithm to be tail recursive, and use the magic form of goto, you can cut the memory growth to zero and achieve some very impressive figures.

8 seconds for 10 million recursions and 83 seconds for 100 million with the memory consumption never over 1.5 MB.

#!/usr/bin/perl -w
use strict;
$|++;

my $count;

deep( $ARGV[ 0 ] );
print $count;

sub deep {
    ++$count and --$_[ 0 ] and goto \&deep;
}
__DATA__
[19:09:45.02] P:\test>422344 10000000
10000000
[19:09:53.02] P:\test> 

[19:10:03.21] P:\test>422344 100000000
100000000
[19:11:26.84] P:\test>
[download]

It takes a little effort to do, but when you need it it is worth it.