Itératif ou récursif ? Analytique.

Dans la lignée de l'article de hier, un benchmark du même type sur la suite de Fibonacci. L'intérêt est ici de montrer que :

• Ruby est lent en récursif : l'appel de fonction est très coûteux en temps cpu (la version 1.9 devrait améliorer ce point, c'est du moins ce qui avait été annoncé).
• Plus que pour sur le cas de la fonction factorielle, on constate que la version itérative est moins claire (et élégante) que la récursive (certes, c'est en partie de ma faute...).
• Lorsqu'on a à disposition une solution analytique, on est gentil : on l'utilise ! (d'autant qu'ici elle utilise le nombre d'or... Pourquoi se priver d'esthétisme ésotérique à la Phidias ?)

Le code :
(testé sous Windows, Ruby 1.8.6)

# Benchmark on Fibonacci

include Math
Sqrt5 = Math.sqrt(5.0)

# Recursive version
def fibo_rec n
    if n < 3 
        1
    else
        fibo_rec(n-1) + fibo_rec(n-2)
    end
end

# Analytic version
def fibo_analy n
    ((1/Sqrt5)*(((1+Sqrt5)/2)**n-((1-Sqrt5)/2)**n)).to_i
end

# Iterative version
def fibo_iter n
    if n < 3
        1
    else
        res1 = 1
        res = 2
        (n-3).times do
            tmp = res
            res += res1
            res1 = tmp
        end
        res
    end
end

# Benchmark
require 'benchmark'

Benchmark.bm(9) do |timer|
    timer.report('Iterative'){
        100.times do fibo_iter(20) end
    }
    timer.report('Analytic') {
        100.times do fibo_analy(20) end
    }
    timer.report('Recursive') {
        100.times do fibo_rec(20) end
    }
end

#=>
#               user     system      total        real
#Iterative  0.016000   0.000000   0.016000 (  0.016000)
#Analytic   0.000000   0.000000   0.000000 (  0.000000)
#Recursive  1.375000   0.000000   1.375000 (  1.375000)