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.
- Is my choice to use '@fib_n' instance variables correct or there is a better choice?
- 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).