我的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);
  }
}