Fibonacci序列子程序返回的值太高

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,这是正确答案.

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

希望这可以帮助!

Answer 2

在斐波那契序列开始于f(0) = 0和f(1) = 1.之后,每个斐波纳契数是前两个的总和.

您的函数使用return (1) if ($num <= 1)错误评估f(0)为1.如果将其更改为,return $num if $num <= 1则序列将正确启动.

此代码输出系列中的前11个数字.

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