我的Fibonacci序列作为递归函数是一个无限循环

Question

下面的函数无限递归，我不明白为什么。它输入条件语句，但似乎不会以return语句结束。

use strict;
use warnings;

print fibonacci(100);

sub fibonacci {

    my $number = shift;

    if ($number == 0) {
        print "return 0\n";
        return 0;
    }
    elsif ($number == 1) {
        print "return 1\n";
        return 1;
    }
    else {
        return fibonacci($number-1) + fibonacci($number-2);
    }
}

Answer 1

你的循环不会无限地递归，它只是在输入为100的情况下花费的时间太长了。尝试使用memoized版本：

{ my @fib;
  sub fib {
    my $n = shift;
    return $fib[$n] if defined $fib[$n];
    return $fib[$n] = $n if $n < 2;
    $fib[$n] = fib($n-1) + fib($n-2);
  }
}

Answer 2

你的代码可以变得更加简洁，并且可以通过记忆来大大提高速度。

到目前为止，Memoize模块是记录(缓存)子例程结果的最简单、最清晰的方法。

我推荐这个版本。它仍然对深度递归发出警告，但它会产生一个我认为是正确的值。

use strict;
use warnings;

use Memoize;
memoize('fibonacci');

print fibonacci(100);

sub fibonacci {
    my ($n) = @_;
    $n < 2 ? $n : fibonacci($n-1) + fibonacci($n-2);
}

输出

Deep recursion on anonymous subroutine at E:\Perl\source\fib.pl line 11.
Deep recursion on anonymous subroutine at E:\Perl\source\fib.pl line 11.
3.54224848179262e+020

Answer 3

您的递归函数调用不是无限的。这需要很长的时间。

人们应该注意递归函数，因为如果可以这样设计的话，使用循环编写代码通常会更好。

在这种情况下，对fibonacci的递归调用数量呈指数级增长。您可以很容易地自己测试这一点，只需简单地添加较低级别的调用

• fibonacci(0) =1 call
• fibonacci(1) =1 call
• fibonacci(2) =1个15
• fibonacci(N) + fibonacci(1)调用+ fibonacci(0) fibonacci(2)调用3
• fibonacci(3) =1个呼叫+ fibonacci(1) fibonacci(3)调用+ fibonacci(2) fibonacci(4)调用+ fibonacci(3)→→=1个→调用+fibonacci(4)+fibonacci(3)→→调用=1个呼叫+ fibonacci(N-1)调用+ fibonacci(N-2)→?

调用

正如您所看到的，子例程调用的数量出现了类似斐波纳契数的增长。

要确定对fibonacci(100)的调用次数，我们可以简单地创建一个快速的perl一行程序：

$ perl -e '
    @c = (1, 1); 
    $c[$_] = 1 + $c[$_-1] + $c[$_-2] for (2..100);
    print $c[100]
  ' 
1.14629568802763e+21

以每秒1万亿次调用的速度计算，这仍然需要31年以上的时间才能完成。

使用Memoize修复

已经提出的一种修复方法是使用核心库Memoize

use Memoize;
memoize('fibonacci');

这个模块将围绕您的子例程调用并缓存数值的计算。因此，这将把你的函数调用次数从1.14e21减少到101次计算。

但是，由于您的递归次数超过100次，因此每个perldiag都会收到以下警告

子例程"%s“上匿名subroutine

• Deep递归的
• 深度递归

(W递归)此子例程(直接或间接)调用自身的次数比返回的次数多100倍。这可能表示无限递归，除非您正在编写奇怪的基准程序，在这种情况下，它表示其他东西。

通过重新编译perl二进制文件，将C预处理器宏PERL_SUB_DEPTH_WARN设置为所需的值，可以将此阈值从100更改为所需的值。

改为创建循环-避免递归

您的算法可以很容易地重新设计，从自上而下的计算方法到自下而上的方法。

这完全消除了对递归的需要，并将代码减少为以下内容：

use strict;
use warnings;

print fibonacci(100), "\n";

sub fibonacci {
    my $number = shift;

    my @fib = ( 0, 1 );

    for ( $#fib + 1 .. $number ) {
        $fib[$_] = $fib[ $_ - 1 ] + $fib[ $_ - 2 ];
    }

    return $fib[$number];
}

输出：

3.54224848179262e+20

不会给出任何警告。