优化递归搜索

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

您在Ruby中的斐波那契实现是正确的。你可以把它改写通过以下方式

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

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

但除此之外，与您的算法相比，在时间上没有成本变化。有一个few possible improvements。众所周知，递归算法比非递归版本慢。

斐波那契递归序列的时间复杂度为O(n^2)（我将跳过计算的详细信息，这里有大量的论文和SO answers这个主题）。有several variations。

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

下面是一个使用Array作为存储的非常快速和肮脏的示例。

$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。我只用一个全局变量作为例子来演示memoization模式。你应该使用一个更好的系统，全局变量几乎被认为是Ruby中的代码味道。

Answer 2

你可以试着为你计算递归斐波那契数，以节省您的结果：

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（披^ N）其中phi =（1 +开方（5））/ 2.

编辑：这是在Python中（没有看到Ruby标签）。应该相当简单地翻译。

Answer 3

长时间运行并不是递归的固有功能，但当您有冗余递归计算时，经常会出现这种情况。可以使用称为“memoization”的技术来避免这种情况，您只需计算一次值并将其存入以备将来使用。

这里是一个memoized递归实现斐波那契数，猴子打补丁到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 

如果你真的想去大，使用斐波那契算法是O的matrix multiplication version（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列线。