Ruby中的Fibonacci序列(递归)

Question

我正在尝试实现以下功能,但它一直给我stack level too deep (SystemStackError)错误.

任何想法可能是什么问题？

def fibonacci( n )
    [ n ] if ( 0..1 ).include? n
    ( fibonacci( n - 1 ) + fibonacci( n - 2 ) ) if n > 1
end

puts fibonacci( 5 )

Answer 1

试试这个

def fibonacci( n )
  return  n  if ( 0..1 ).include? n
  ( fibonacci( n - 1 ) + fibonacci( n - 2 ) )
end
puts fibonacci( 5 )
# => 5

查看这篇文章太斐波那契One-Liner

以及更多.. https://web.archive.org/web/20120427224512/http://en.literateprograms.org/Fibonacci_numbers_(Ruby)

你现在已被许多解决方案轰炸:)

关于你解决方案中的问题

你应该回来,n如果它0或1

并且add最后两个数字不是最后一个

新修改版

def fibonacci( n )
    return  n  if n <= 1 
    fibonacci( n - 1 ) + fibonacci( n - 2 )
end 
puts fibonacci( 10 )
# => 55

一个班轮

def fibonacci(n)
   n <= 1 ? n :  fibonacci( n - 1 ) + fibonacci( n - 2 ) 
end
puts fibonacci( 10 )
# => 55

Answer 2

这是我想出的东西,我发现这更直接.

def fib(n)
  n.times.each_with_object([0,1]) { |num, obj| obj << obj[-2] + obj[-1] }
end
fib(10)

Answer 3

这不是你计算斐波纳契的方法,你正在创建一个巨大的递归树,它会因为相对较小的ns 而失败.我建议你这样做:

def fib_r(a, b, n)
  n == 0 ? a : fib_r(b, a + b, n - 1)
end

def fib(n)
  fib_r(0, 1, n)
end

p (0..100).map{ |n| fib(n) }

Answer 4

线性

module Fib
  def self.compute(index)
    first = 0
    second = 1
    index.times do
      third = first + second
      first = second
      second = third
    end
    first
  end
end

递归缓存

module Fib
  @@mem = {}
  def self.compute(index)
    if index <= 1
      return index
    else
      @@mem[index] ||= compute(index-1) + compute(index-2)
    end
  end
end

如果你打电话,这些解决方案都不会使你的系统崩溃 Fib.compute(256)

Answer 5

这种方法很快并且使用了memoization:

fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }

fib[123] # => 22698374052006863956975682

如果你想知道这个哈希初始化是如何工作的,请阅读:

https://ruby-doc.org/core/Hash.html#method-c-new

Answer 6

PHI = 1.6180339887498959
TAU = 0.5004471413430931

def fibonacci(n)
  (PHI**n + TAU).to_i
end

你不需要递归.

Answer 7

递归非常慢,这是一种更快的方法

a = []; a[0] = 1; a[1] = 1
i = 1
while i < 1000000
    a[i+1] = (a[i] + a[i-1])%1000000007
    i += 1
end

puts a[n]    

它是O(1),但你可以使用矩阵求幂,这是我的一个实现,但它在java => http://pastebin.com/DgbekCJM,但矩阵exp.的O(8logn).这是一个快得多算法,称为快速加倍.这是一个快速加倍的java实现.

class FD {

    static int mod = 1000000007;

    static long fastDoubling(int n) {
        if(n <= 2) return 1;
        int k = n/2;
        long a = fastDoubling(k+1);
        long b = fastDoubling(k);
        if(n%2 == 1) return (a*a + b*b)%mod;
        else return (b*(2*a - b))%mod;
}

然而,使用karatsuba乘法,矩阵exp.并且快速加倍变得快得多,但快速加倍节拍矩阵exp.通过一个恒定的因素,我不想在这里非常彻底.但我最近做了很多关于斐波纳契数的研究,我希望我的研究对任何愿意学习的人都有用;).