如何在Ruby中使用recrusion编写fibonacci序列？

Question

我曾尝试在Ruby中创建一个方法，如果包含数字fibonacci-sequence则返回true，如果不包含则返回false。

当我返回true或false时，我想我遇到了一个问题。

有人能告诉我为什么第一个代码不能工作吗？

def is_fibonacci?(num, array=[0,1])

  n = array.length - 1

  if array[n] > num
    array.include?(num) ? true : false
  end

  array << array[n] + array[n-1]
  is_fibonacci?(num, array)

end

当我运行这段代码时，我得到了这个错误消息。

=>filename.rb:36:in‘`include?'：中断

def is_fibonacci?(num, array=[0,1])
  n = array.length - 1

  if array[n] > num
    if array.include?(num)
        return true
    else
        return false
    end
  end

  array << array[n] + array[n-1]
  is_fibonacci?(num, array)

end

第二个代码起作用了。

为什么我不能使用

array.include?(num) ? true : false 

在代码中？

谢谢你的帮助。

Answer 1

Shivam已经很好地回答了为什么你的第一个版本不能工作的问题。

我只想指出，没有理由将所有计算出的斐波那契数都保存在数组中。这是对空间的浪费，而且效率可能有点低。因此，您可以将您的方法简化为：

def fibonacci?(number)
  fibos = [0, 1]
  fibos << (fibos.shift + fibos.last) while fibos.last < number
  fibos.include?(number)
end

Answer 2

array.include?(num) ? true : false不工作的原因是因为您没有return语句。将其更改为return array.include?(num) ? true : false。WIthout，它只会调用另一个级别的递归算法，最后会运行到堆栈太深的地方。

作为额外的奖励，下面是使用散列的著名一行代码：

fibonacci = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }

p fibonacci[2]  # => 1
p fibonacci[23] # => 28657

Answer 3

为什么我不能使用array.include?(num) ? true : false

从语法上讲，这条语句没有任何错误，应该可以很好地工作。(它可能会返回SystemStackError: stack level too deep，但在您的代码上下文中，因为您没有返回任何值)。

下面是一个示例：

array = [0,1]
num = 1
array.include?(num) ? true : false
# => true
num = 3
array.include?(num) ? true : false
# => false

然而，这是一段可怕的代码。.include?的官方文档明确指出：

如果给定对象存在于self中(即，如果任何object == anObject)，则

返回true，否则返回false。

这意味着：

num = 1
array.include?(num)
# => true
num = 3
array.include?(num)
# => false

您再次在以下代码中重复相同的错误：

 if array.include?(num)
    return true
 else
    return false
 end

上面的所有代码都可以用一行代码替换：

return array.include?(num)