ruby - 优化递归搜索

Question

我进行了一个实验来计算递归与迭代斐波那契数列的时间。有没有更好的方法来提高我的递归方法的性能？

require 'benchmark'

def fibonacci_iterative(n)
  fib_numbers = [0, 1]
  iterate = n-1
  iterate.times do
    number = fib_numbers[-2] + fib_numbers[-1]
    fib_numbers << number
  end
  p fib_numbers[-1]
end

def fibonacci_recursive(n)
  fib_number = 0
  if n == 0 || n == 1
    n
  else
    fib_number = fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
  end
end

puts Benchmark.measure {fibonacci_iterative(5)}
puts Benchmark.measure {fibonacci_recursive(5)}

5
  0.000000   0.000000   0.000000 (  0.000037)
  0.000000   0.000000   0.000000 (  0.000005)

puts Benchmark.measure {fibonacci_iterative(45)}
puts Benchmark.measure {fibonacci_recursive(45)}

1134903170
  0.000000   0.000000   0.000000 (  0.000039)
378.990000   0.330000 379.320000 (379.577337)

这是递归的固有特征吗？

Answer 1

运行时间长并不是递归的固有功能，但当你有冗余的递归计算时，它经常会出现。可以使用一种称为“记忆化”的技术来避免这种情况，在这种技术中，您只需计算一次值并将它们制成表格以供将来使用。

这是斐波那契数列的内存递归实现，猴子修补成 Fixnum...

class Fixnum
  @@fib_value = [0,1]

  def fib
    raise "fib not defined for negative numbers" if self < 0
    @@fib_value[self] ||= (self-1).fib + (self-2).fib
  end
end

0.fib     # => 0
1.fib     # => 1
2.fib     # => 1
5.fib     # => 5
100.fib   # => 354224848179261915075

如果你真的想变大，使用 matrix multiplication version斐波那契算法的复杂度为 O(log n):

class Fixnum
  def fib
    raise "fib not defined for negative numbers" if self < 0
    self.zero? ? self : matrix_fib(self)[1]
  end

  private

  def matrix_fib(n)
    if n == 1
      [0,1]
    else
      f = matrix_fib(n/2)
      c = f[0] * f[0] + f[1] * f[1]
      d = f[1] * (f[1] + 2 * f[0])
      n.even? ? [c,d] : [d,c+d]
    end
  end
end

45.fib  # => 1134903170 confirms correctness

您几乎可以在瞬间计算出 1000000.fib 而不会耗尽递归堆栈，尽管输出超过 2600 行 80 列。