How to redefine warnings on recursion level

[Gerhard M]

first of all an simple program:

use Math::BigInt;
use warnings;

my $v = new Math::BigInt;
sub faculty ($);

$v= faculty($ARGV[0]);
print $v,"\n";

sub faculty ($) {
my $v=shift;
return ( $v>1 ? $v*faculty($v -1) : 1 );
}

If executing with argument 99 there's no problem, but if using 100 as
argument i'll get the warning:
Deep recursion on subroutine "main::faculty" at recursive.pl line 13.

1) How can i redefine the recursion level to keep down this warning?
2) Is it possible to add a level of recursion to die the program
(instead to warn)?

regards
gerhard

 

[Paul Lalli]

first of all an simple program:

use Math::BigInt;
use warnings;

my $v = new Math::BigInt;
sub faculty ($);

$v= faculty($ARGV[0]);
print $v,"\n";

sub faculty ($) {
my $v=shift;
return ( $v>1 ? $v*faculty($v -1) : 1 );
}

If executing with argument 99 there's no problem, but if using 100 as
argument i'll get the warning:
Deep recursion on subroutine "main::faculty" at recursive.pl line 13.

1) How can i redefine the recursion level to keep down this warning?

perldoc perldiag says:
(W recursion) This subroutine has called itself (directly or
indirectly)
100 times more than it has returned. This probably indicates an
infinite recursion, unless you're writing strange benchmark
programs, in
which case it indicates something else.

If you're sure that your program should be recursing over 100 times,
then simply turn off this warnings:

no warnings 'recursion';

2) Is it possible to add a level of recursion to die the program
(instead to warn)?

Check out %SIG as described in perldoc perlvar


I think the question has to be asked - why are you doing this? If this
was just a sample to show us the warning message, that's fine. But if
this is how you're actually calculating a factoral (which is the
mathematical term for what you're doing - not "faculty"), have you
considered an iterative algorithm instead?

my $fact = 1;
$fact *= $_ for (1..100);
print "100! = $fact\n";

Paul Lalli

 

[thundergnat]

first of all an simple program:

use Math::BigInt;
use warnings;

my $v = new Math::BigInt;
sub faculty ($);

$v= faculty($ARGV[0]);
print $v,"\n";

sub faculty ($) {
my $v=shift;
return ( $v>1 ? $v*faculty($v -1) : 1 );
}

If executing with argument 99 there's no problem, but if using 100 as
argument i'll get the warning:
Deep recursion on subroutine "main::faculty" at recursive.pl line 13.

1) How can i redefine the recursion level to keep down this warning?

see below

2) Is it possible to add a level of recursion to die the program
(instead to warn)?
yes


regards
gerhard

use Math::BigInt;
use warnings;

my $v = new Math::BigInt;
my $limit = 150;
my $level;
sub faculty ($);

$v= faculty($ARGV[0]);
print $v,"\n";

sub faculty ($) {
no warnings qw/recursion/;
my $v=shift;
if($v>1){
$level++;
die 'Deep recrusion' if $level > $limit;
return $v*faculty($v -1);
}else{
return 1;
}
}

 

[Tad McClellan]

sub faculty ($) {
my $v=shift;
return ( $v>1 ? $v*faculty($v -1) : 1 );
}

Deep recursion on subroutine "main::faculty" at recursive.pl line 13.

1) How can i redefine the recursion level to keep down this warning?

You do not need to redefine the recursion level to suppress the
warning, simply disable the warning:

sub faculty ($) {
my $v=shift;
{ no warnings 'recursion';
return ( $v>1 ? $v*faculty($v -1) : 1 );
}
}

 

[Jon Ericson]

[Have] you considered an iterative algorithm instead?

Yes, i've thougt about it. Thats my code:

%all=();
...
sub insert ($$$) {
my ($key,$data;$cnt)=@_;
if (defined $all{$_[0]."[".$_[2]."]"}) { # already exists
insert($key, $data, ++$cnt);
} else { # insert data
$all{$_[0]."[".$_[2]."]"} = $data
}
}

This also could be done with an iterative algorithm. The recursion was
my first idea and it works (except the warning). It's easy to
understand so why to change it?

I wouldn't say it's easy to understand. That looks like a really poor
candidate for a recursive function -- especially if it's called
recursively hundreds of times. For that matter, it shouldn't be done
iteratively either.

remark:
It's a stupid way build up "a kind of" arrays. Better it should have
be done with something like "push (@{$all{key}}, $data)". But the
other routines using %all are only able to handle simple variables in
%all.

Seems like it might be worth a redesign.

Jon

 

[Jon Ericson]

Jon Ericson ([email protected]) wrote on MMMMLXIX September
MCMXCIII in <URL:news:[email protected]>:

-: Depending on how often a script calculates factorial, it's possible a
-: memoized recursive algorithm would be a win. Consider 100! - 98!, for
-: instance.


my $sum = 100 * 98;
$sum *= $_ for 2 .. 98;

$ perl -e '$s = 100*98;$s*=$_ for 2..98;print "$s\n"'
9.23835263990558e+157

The correct answer is:

$ perl -e '$a=$s=1;$a*=$_ for 2..98;$s=$a*99*100-$a;print "$s\n"'
9.33167885534952e+157

But what's a few, umm, 10**155 between friends? ;-)

In either case, the more realist example would be x! - y! repeated
many times for arbitrary values of x and y.

Jon

 

[Jon Ericson]

Jon Ericson ([email protected]) wrote on MMMMLXX September
MCMXCIII in <URL:news:[email protected]>:

== In either case, the more realist example would be x! - y! repeated
== many times for arbitrary values of x and y.


x! - y! == (x * (x - 1) * (x - 2) ... * (y + 1) - 1) * y!


sub facdiff {
local $" = "*";
eval "(@{[($_ [1] + 1) .. $_ [0]]} - 1) * @{[1 .. $_ [1]]}";
}

Hmmm... facdiff(100, 100) = -9.33262154439441e+157 ?!?

Clever, though.

Jon

 

[Joe Smith]

This also could be done with an iterative algorithm. The recursion was
my first idea and it works (except the warning). It's easy to
understand so why to change it?

Efficiency. Have you checked how much slower recursion is in this case?
-Joe