algorithm - 斐波那契序列子例程返回的值太高

Question

#!/usr/bin/perl -w
use strict;

sub fib {
    my($num) = @_;  #give $num to input array
    return(1) if ($num<=1);  #termination condition
    return($num = &fib($num-1) + &fib($num-2));  #should return sum of first "n" terms in the fibonacci sequence
}

print &fib(7)."\n";  #should output 20

这个子例程应该输出第一个“x”个项的总和，由 sub 的参数指定。但是，它太高了。这与递归有关吗？

谢谢。

Answer 1

20 不是斐波那契数。最接近的是21，第九。序列的第一项是

0 1 1 2 3 5 8 13 21

你的程序输出 21，这是正确的答案。

如果要计算第一个斐波那契数的总和n，则需要更新代码。现在你只是在计算n斐波那契数。如果您想要第一个n斐波那契数的总和，您应该使用当前函数作为子程序来计算 F(n + 2) - 1。

希望这可以帮助！

Answer 2

斐波那契数列以f(0) = 0和开头f(1) = 1。之后，每个斐波那契数是前两个数的总和。

您的函数使用return (1) if ($num <= 1)which 错误地评估f(0)为 1。如果您将其更改为，return $num if $num <= 1那么您的序列将正确启动。

此代码输出系列中的前十一个数字。

use strict;
use warnings;

sub fib {
  my ($num) = @_;
  if ($num <= 1) {
    return $num;
  }
  else {
    return fib($num-1) + fib($num-2);
  }
}


print join ' ', map fib($_), 0 .. 10;

输出

0 1 1 2 3 5 8 13 21 34 55

Answer 3

templatetypedef 已经回答了这个问题，但我想警告你，你的实现很糟糕。如果你有足够的时间，它会给你正确的答案，但除非你不在乎等待几个世纪，否则你应该真正以不同的方式计算斐波那契数列。确实要计算fib(n)两次fib，这意味着计算的复杂度fib(n)是 O(fib(n))。您可以非常简单地实现 O(n) 复杂度，甚至可以达到 O(Log(n)) 复杂度，只需查看Wikipedia即可。