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 是一个全局包，不是子例程的词法范围。这个（和类似的）问题在使用递归实现时起作用的原因是它们通常是使用词法范围变量编写的。这些作用域存储递归展开时所需的状态。对于您的代码，不会存储任何状态，因为您只是一遍又一遍地重复使用相同的变量。如果您要在 shift 之后立即放置一个 print "$n\n";，您会看到 $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 创建了一个词法范围的变量，可用于在每个级别分别维护状态递归调用堆栈，而您正在使用的全局包只有一个状态。

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

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

perl

dynamic-programming

fibonacci

memoization