斐波纳契递归红宝石解释

Question

我知道如何在没有递归的情况下解决这个问题,但有了它,我有一些难以理解......我需要深入解释它是如何逐行工作的

以下是问题的解决方法:

def fibo(num)
  if num < 2
    num
  else
    #this is where I get lost on the line below..
    fibo(num-1) + fibo(num-2)
  end
end

p fibo(6)

Answer 1

在Fibonacci序列中,前两个序列之后的序列中的每个数字是前两个数字的总和:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

当你写一个递归函数,你明确地处理基地的情况下(这是fibo(0)和fibo(1)你的情况),然后什么都可以通过调用你正在写的功能,通过对早期的经营建立后的结果来计算.

根据定义,在序列中的前2个数字之后,斐波纳契数是前2个数的总和.换句话说,fibo(n)= fibo(n-1)+ fibo(n-2).这就是这行代码所做的事情:

fibo(num-1) + fibo(num-2)

它通过为前两个数字调用自身(即"递归")并将它们加在一起来返回fibo(num)的值.

因为它们是基本情况,我们知道fibo(0)将为0,而fibo(1)将为1.让我们看看这对于fibo(4)是如何工作的:

fibo(4) = fibo(3) + fibo(2)
fibo(4) = (fibo(2) + fibo(1)) + (fibo(1) + fibo(0))
        = (fibo(2) +    1   ) + (   1    +    0   )
        = (fibo(2) + 2)
        = ((fibo(1) + fibo(0)) + 2
        =     1     +    0     + 2
        = 3

因此,程序最终通过将每个计算分解为更简单的问题来计算正确的结果,直到它到达已定义答案的基本情况.请注意,这不是很有效,因为它fibo被称为9次计算fibo(4).