优化递归搜索

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

长运行时间不是递归的固有函数，但当您有多余的递归计算时，它经常会出现。可以避免使用一种名为"记忆"的技术，即只计算一次值并将其表化以备将来使用。

这是Fibonacci数的记忆递归实现，猴子补丁到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

如果你真的想做大，可以使用Fibonacci算法的矩阵乘法版本，即O(logn):

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，而不会破坏递归堆栈，尽管输出超过260080列线。

Answer 2

您在Ruby中的Fibonacci实现是正确的。你可以用以下方式重写

def fib(n)
if n < 2
n
else
fib(n-1) + fib(n-2)
end
end

唯一的优点是它更简洁一点，而且你不需要使用任何额外的变量，事实上，这是不需要的。

但除此之外，与您的算法相比，在时间方面没有成本变化。有一些可能的改进。众所周知，递归算法比非递归版本慢。

Fibonacci递归序列的时间复杂度是O(n^2)(我将跳过计算的细节，关于这个主题有很多论文和SO答案)。有几种变体。

一个快速改进是添加缓存。这将减少序列中相同子数的计算。

下面是一个使用数组作为存储的快速而肮脏的示例。

$cache = []
def fib(n)
$cache[n] ||= if n < 2
n
else
fib(n-1) + fib(n-2)
end
end

只是为了好玩，这里有一个更紧凑、独立的替代

def fib(n)
$fibcache    ||= []
$fibcache[n] ||= (n < 2 ? n : fib(n-1) + fib(n-2))
end

PS。我只使用了一个全局变量作为示例来演示记忆模式。你应该使用一个更好的系统，全局变量在Ruby中几乎被认为是一种代码气味。

Answer 3

您可以在计算递归fibonacci:时尝试保存结果

def fibonacci_recursive(n):
def fib_rec(n, a, b):
if n == 1:
return a
return fib_rec(n - 1, a + b, a)
return fib_rec(n, 1, 0)

递归代码具有指数行为：O(phi^n)，其中phi=(1+sqrt(5))/2。

编辑：这是在Python中(没有看到Ruby标记)。翻译应该相当简单。