go ahead... be a heretic PerlMonks

### Re^2: Who's a thief? -- the follow up

by Ovid (Cardinal)
 on Jan 14, 2005 at 17:15 UTC ( #422323=note: print w/replies, xml ) Need Help??

He does that in Chapter 15 of ANSI Common Lisp, but I never checked it out. Thanks for the pointer. I tried working through the implementation in Structure and Interpretation of Computer Programs, but it quickly got a bit too hairy for me. I'll look at Paul Graham's version more closely, but one problem that happens with larger systems like this is the systems tend to rely heavily on recursion and this is not Perl's strength :/ Lisp and Scheme don't have this problem.

Cheers,
Ovid

New address of my CGI Course.

Replies are listed 'Best First'.
Re^3: Who's a thief? (recursion limitations)
by sleepingsquirrel (Hermit) on Jan 14, 2005 at 18:29 UTC
...one problem that happens with larger systems like this is the systems tend to rely heavily on recursion and this is not Perl's strength :/
You're not giving perl enought credit for what it can do. The following program executes in under 9 seconds on my (1GB) machine.
```#!/usr/bin/perl -w

print deep(2_500_000);

sub deep
{
\$_[0]>0 ? deep(\$_[0]-1) : "done\n";
}
...and I can calculate the 36th fibonacci number using the simplistic algorithm below in about a minute. It ends up calling "fib" over 48 million times.
```#!/usr/bin/perl -w

\$count = 0;
my \$n = (\$ARGV[0] < 1) ? 1 : \$ARGV[0];
print fib(\$n)."\ncount = \$count\n";

sub fib { \$count++; \$_[0]<2 ? 1 : fib(\$_[0]-2) + fib(\$_[0]-1) }

-- All code is 100% tested and functional unless otherwise noted.

As soon as I tried your "deep" program, I immediately got a "deep recursion" error. I've a 1.6 GHz machine with 640 megs of RAM. I don't know how you could have run that. Every time Perl enters a sub (normally), it creates a new stack frame and this quickly eats memory.

On my machine, it pretty much ground the box to a halt after about 1.5 million iterations.

Cheers,
Ovid

New address of my CGI Course.

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>

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

Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.
Ovid,
Every time Perl enters a sub (normally), it creates a new stack frame and this quickly eats memory.

Presumably, you are referring to &sub as the abnormal example where you could use goto &sub to bypass the recursion limit as seen in the following example:

```#!/usr/bin/perl
use strict;
use warnings;

print sum( 1000 );
sub sum {
my (\$num, \$tot) = @_;
return \$tot if ! \$num;
@_ = (\$num - 1, \$tot += \$num);
goto &sum;
}
According to TimToady, this actually does create a new stack, but only after the old one is stripped off. Of course you could always ignore the warning, turn off the 'recursion' warning, or recompile Perl to avoid the warning. In practice, I have never needed this kind of technique because it seems that iterative solutions aren't that difficult to come up with. In this case, the formula (n^2 + n) / 2 would do the trick.

And as I am previewing this, I see BrowserUk has already said something similar - oh well.

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://422323]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (7)
As of 2019-10-16 23:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (42 votes). Check out past polls.

Notices?