为什么我的函数在ruby中输出期望值和意外值

Question

我有一个名为fibs_rec的方法，它会导致意外输出：

def fibs_rec(n)
if n == 1 || n == 0 
return 1 
else 
a = fibs_rec(n-1) + fibs_rec(n-2) 
puts a
return a 
end 
end 
fibs_rec(5)

调用fibs_rec(5)应该返回1,1,2,3,5，但这里是实际输出：

2
3
2
5
2
3
8

输出不仅不正确，而且从一开始就缺少一个数字。

有人能解释为什么会发生这种情况吗？

Answer 1

这是正确的，因为每次递归都会分解为两个子问题。如果你想让这个系列正确地出现，那么你应该尝试通过O(n)时间复杂性的动态编程来做到这一点。按原样，由于递归中的基本情况，第一个和第二个位置将不会打印。

至于错误的答案，您似乎没有考虑到以0索引开头的序列。在将给出第五个元素的函数中找到4索引，或者修改函数以使用位置而不是索引。