Optimize Recursive Search

Question

I ran an experiment to time a recursive versus iterative fibonacci sequence. Is there a better way to improve my recursive method's performance?

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)

Is this an inherent feature of recursion?

Answer 1

Your Fibonacci implementation in Ruby is correct. You can rewrite it in the following way

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

The only advantage is that it's a little bit more concise and you don't use any additional variable that, in fact, it's not required.

But apart from that, there is no cost change in terms of time compared to your algorithm. There are a few possible improvements. The recursive algorithm is well known to be slower than the non recursive version.

The Time Complexity of the Fibonacci recursive sequence is O(n^2) (I'll skip the details of the calculation, there are tons of papers and SO answers available on the topic). There are several variations.

One quick improvement is to add a cache. This will reduce the computation of the same sub-number in the sequence.

Here's a very quick and dirty example using an Array as storage.

$cache = []

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

Just for fun, here's a more compacted, self-contained alternative

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

PS. I used a global variable only as example to demonstrate the memoization pattern. You should use a better system, global variables are almost considered a code smell in Ruby.

Answer 2

The long run-time isn't an inherent function of recursion, but will often come up when you have redundant recursive calculations. It can be avoided using a technique called "memoization", where you calculate values only once and table them for future use.

Here's a memoized recursive implementation of Fibonacci numbers, monkey-patched into 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

If you really want to go large, use the matrix multiplication version of the Fibonacci algorithm which is 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

You can calculate 1000000.fib nearly instantaneously and not blow out the recursive stack, although the output is over 2600 80-column lines.

Answer 3

You can try to save your results as you compute the recursive 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)

Your recursive code has exponential behaviour: O(phi ^ n) where phi = (1 + sqrt(5)) / 2.

EDIT: This is in Python (didn't see the Ruby tag). Should translate fairly simply.