Ruby 斐波那契算法

Question

下面是我写的一个计算斐波那契数列中的值的方法:

def fib(n)

    if n == 0
        return 0
    end
    if n == 1
        return 1
    end

    if n >= 2
        return fib(n-1) + (fib(n-2))
    end

end

它工作到 n = 14，但在那之后我收到一条消息说程序响应时间太长(我正在使用 repl.it)。有人知道为什么会这样吗？

Answer 1

Naive fibonacci 进行了大量的重复计算 - 在 fib(14) fib(4) 中计算了很多次。

您可以将内存添加到您的算法中以使其更快:

def fib(n, memo = {})
  if n == 0 || n == 1
    return n
  end
  memo[n] ||= fib(n-1, memo) + fib(n-2, memo)
end
fib 14
# => 377
fib 24
# => 46368
fib 124
# => 36726740705505779255899443