# Ruby Fibonacci(n) recursive computation optimized with reflection

The idea is to take the common-known (and awfully bad performing) Fibonacci(n) recursive method:

# recursively computate fibonacci(n)
def fib(n)
n <= 2 ? 1 : fib(n-2) + fib(n-1)
end


and to optimize it with some Ruby reflection:

require 'benchmark'

def fib(n)
# if n<= 2 fib(n) = 1
return 1 if n <= 2
# if @fib_n is defined it means that another instance of this method
# has already computed it, so I just return its value
return instance_variable_get("@fib_#{n}") if instance_variable_get("@fib_#{n}")
# else I have to set fib_n and return its value
instance_variable_set("@fib_#{n}", ( fib(n-2) + fib(n-1) ) )
end

Benchmark.bm(30) do |x|
x.report("fibonacci(#{ARGV[0]}) computation time:") {$fib = fib(ARGV[0].to_i)} end puts "fib(#{ARGV[0]}) = #{$fib}"


Since the execution time for fib(36) drops from about 4 sec to 0.000234 sec, I guess it's working! But since I'm a Ruby novice (and since this is my first attempt with reflection), I'd still like to have my code peer-reviewed.

1. Is my choice to use '@fib_n' instance variables correct or there is a better choice?
2. Does anyone know a better Ruby optimization for the recursive computation of Fibonacci members? (I know, the most efficient computation for Fibonacci is the iterative one, but here I'm strictly interested in the recursive one).
• I would suggest using an array instead of instance variables May 31, 2012 at 18:26
• How and why? How about a comprehensive answer? I'm still waiting for one to accept. May 31, 2012 at 19:44
• I gave your suggestion a try but I used... an instance array. See the update: it is 5 times faster, thank you. Jun 1, 2012 at 8:20
• Recursion isn't my bottleneck... Check it out: stackoverflow.com/questions/23749877/… May 20, 2014 at 3:23

considering that this is Code Review, I have to say that you probably don't want to use an instance variable. You expose the internal data, and any user could destroy the workings of your method inadvertently. In Ruby 1.9, Ruby added a very interesting feature for just these types of situations that involve infinite sequences. It's called a Fiber.

It's true that Fibers aren't perfect for situations where you have to go backwards in the sequence in addition to forward.

Another option for this is to put the data in a module:

module Fibonacci
@fib=[0,1,1]
def self.fib_array(n)
@fib[n] ||= fib_array(n-2) + fib_array(n-1)
end
end


And use it like so:

Fibonacci.fib_array(42)


One possible solution with lambda:

fibp =
lambda do
a = [0, 1]
lambda do |n|
if n > 1
a[n] ||= fibp[n - 2] + fibp[n - 1]
else
n
end
end
end \
.call

p fibp[1000]


Still prone to stack overflow as any recursive method in Ruby.

UPDATE: In fact memoizing is not necessary if all you need is just one result:

fibp =
lambda do |n|
if n > 1
p1, p2 = fibp[n - 1]
[p2, p1 + p2]
else
[0, n]
end
end

p fibp[1000].last

• You're right: using an array is faster than using single variables but I found this lambda solution being less convenient than the others. It is faster than my first one but slower than my second one (partially based on your suggestion), and overflows the stack a lot before the other approaches does. Jun 1, 2012 at 8:18