Fibonacci Perl程序甚至在使用Memoization之后即使对于小输入也会耗尽内存,

Question

该程序:

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);

即使是小值,即F(3),F(2)我收到此错误:

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

Answer 1

在$n您使用的是一个包全局,而不是词法范围的子程序.使用递归实现此(和类似)问题的原因是它们通常使用词法范围的变量编写.这些范围存储在递归展开时所需的状态.在您的代码的情况下,没有存储状态,因为您只是反复重复使用相同的变量.如果你要print "$n\n";在shift你看到之后立即$n设置为10,那么9,8,7,6,5,4,3,2,1,-1,-2,-3等等.递归正在消失.

更改您的代码如下,它将工作:

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";

这将产生55的预期产量.

代码与这种看似无关紧要的更改(添加my)一起工作的原因是my创建一个词法范围的变量,可以用于在递归调用堆栈的每个级别单独维护状态,而一个包全局,就像你使用它一样,只有一个州.