Recursive Factorial with an mistake

We used factorial in the example about recursion, so let's use it here too:

examples/recursive_factorial_bad.pl

use strict;
use 5.010;

sub factorial {
    my ($n) = @_;
    return factorial($n-1)*$n;
    return 1 if $n == 0;
}

say factorial(6);

If you run the above code it will just keep running and running and either it will choke your computer, crash when you run out of free memory, or you get fed up and press Ctrl-C. It won't even warn you!

Of course you'd not write such code as you always use warnings. As in this version:

examples/recursive_factorial_warnings.pl

use strict;
use warnings;
use 5.010;

sub factorial {
    my ($n) = @_;
    return factorial($n-1)*$n;
    return 1 if $n == 0;
}

say factorial(6);

This will also try to exhaust your computer, but at least it will give you a warning

Deep recursion on subroutine "main::factorial" at recursive_factorial_warnings.pl line 7.

Fatal Warning

If you want to make sure your code stops when you encounter a recursion that has passed the limit of 100 deep recursive calls, you can turn each warning into an exception by writing:

use warnings FATAL => 'all';

Alternatively you can look up the specific category in the hierarchy of warnings and turn only the recursive warnings into fatal exceptions as we did in our example:

examples/recursive_factorial_fatal_warnings.pl

use strict;
use warnings FATAL => 'recursion';
use 5.010;

sub factorial {
    my ($n) = @_;
    return factorial($n-1)*$n;
    return 1 if $n == 0;
}

say factorial(6);

This will throw an exception once you reached the 100s iteration.

How to deal with the Deep recursion on subroutine warning turned exception?

First of all, you probably need to look at the code and figure out what is the bug that causes the deep recursion? Maybe you put the stop condition after the recursive call?

OK we can fix that by swapping the two lines with "return" and we get 720 as a result.

examples/recursive_factorial_fixed.pl

use strict;
use warnings FATAL => 'recursion';
use 5.010;

sub factorial {
    my ($n) = @_;
    return 1 if $n == 0;
    return factorial($n-1)*$n;
}

say factorial(6);

We can even call this passing 98 and we get 9.42689044888324e+153 as a result.

What if we pass 99 ?

We get the dreaded Deep recursion warning turned into exception.

This time however we really wanted to have more than 99 recursive calls.

How to write deep recursions?

So what do you do if you really want to have a recursion that is more than 100 deep?

First of all you might want to reconsider. In almost every case when you feel the urge to have such deep recursions, you are probably better off with a flat solution. So consider rewriting the algorithm.

If you cannot do that or don't want to do that, hey, this might be an school exercise in writing deep recursions :), then you can turn off the warnings.

In this example we turned on all the warnings and then turned off specifically the recursive warnings. I've included a lame print of an undefined value, just to show that while we don't get the Deep recursion on subroutine warning, we still get the Use of uninitialized value warning.

examples/recursive_factorial_no_warnings.pl

use strict;
use warnings;
no warnings 'recursion';
use 5.010;

sub factorial {
    my ($n) = @_;
    return 1 if $n == 0;
    return factorial($n-1)*$n;
}

say factorial(100);

my $c;
say $c;

9.33262154439441e+157
Use of uninitialized value $c in say at

Finding the source of deep recursion

Recently I have encountered the Deep recursion problem in the script that sends out the notification email messages to the subscribers of the Perl Maven site. I've reported it here.

One thing I don't know yet, is where that call comes from so the next thing I'll do is include -d:Confess in the calling of the script. After installing Devel::Confess