Fibonacci Perl program going out of Memory even for Small inputs, even after using Memoization,

Question

The Program:

use warnings;
use Memoize;
memoize ('F');

sub F{
 $n = shift;
 return 0 if $n==0;
 return 1 if $n ==1;
 return F($n-1)+F($n-2);
}

print F(10);

Even for small value viz F(3), F(2) I am getting this error:

Deep recursion on anonymous subroutine at 5.pl line 13.
Out of memory!

Answer 1

The $n you are using is a package global, not lexically scoped to the subroutine. The reason that this (and similar) problems work when implemented using recursion is that they are typically written using lexically scoped variables. Those scopes store state which is needed as the recursion unwinds. In the case of your code no state is stored because you're just reusing the same variable over and over. If you were to put a print "$n\n"; immediately after the shift you would see that $n is set to 10, then 9, 8, 7, 6, 5, 4, 3, 2, 1, -1, -2, -3, and so on. The recursion is running away.

Change your code as follows, and it will work:

use strict;
use warnings;
use Memoize;
memoize('F');

sub F{
  my $n = shift; # Notice "my", creating an instance of $n lexically scoped
                 # to the subroutine. A new instance is tracked for each call.
  return 0 if $n == 0;
  return 1 if $n == 1;
  return F($n-1)+F($n-2);
}

print F(10), "\n";

This will yield the expected output of 55.

The reason that the code works with such a seemingly insignificant change (adding my) is that my creates a lexically scoped variable which can be used to maintain state separately at each level of the recursive call stack, whereas a package global, as you are using it, has just a single state.