lundi 18 février 2008

Iterative, recursive ou tail-recursive ?

Théoriquement, la récursion terminale est une forme optimisée de la récursivité : comme on ne s'enfonce que d'un cran dans la pile, on est sensé avoir des performances similaires à une méthode itérative équivalente.

Cependant, comme le montre le petit benchmark suivant, sur le cas simple de la fonction factorielle, Ruby n'optimise pas la récursion terminale, et c'est bien dommage. A noter que le langage fonctionnel Scheme (dont on va reparler très prochainement) a pour spécification de toujours optimiser la récursion terminale. Ruby 1.9 améliore-t-il les performances sur ce point ?

Code :
(testé sous Windows XP ; Ruby 1.8.6)

# Benchmark on factorial function
#Recursive, tail-recursive
#and iterative versions

# Naive recursive version
def fact_rec_naive num
if num == 0
1
else
fact_rec_naive(num-1)*num
end
end

# Tail recursive version
def fact_rec_tail num
def iterer n, acc
if n <= 1
acc
else
iterer(n-1, n*acc)
end
end
iterer(num,1)
end

# Iterative version
def fact_iter num
res = 1
(1..num).each do |i|
res *= i
end
res
end

# Benchmark
require 'benchmark'

Benchmark.bm(15) do |timer|
timer.report('Naive recursive') {
for i in (0...1000)
fact_rec_naive i
end
}
timer.report('Tail recursive') {
for i in (0...1000)
fact_rec_tail i
end
}
timer.report('Iterative') {
for i in (0...1000)
fact_iter i
end
}
end

#=>
# user system total real
#Naive recursive 4.281000 0.062000 4.343000 ( 4.344000)
#Tail recursive 4.735000 0.063000 4.798000 ( 4.812000)
#Iterative 3.640000 0.015000 3.655000 ( 3.672000)





Références :

2 commentaires:

Lefty a dit…

p'tain, récursion terminale, ça fait science-fiction, style, je sais pas moi, chambres à gaz.
non, je confonds, c'était la solution finale...

Sobe a dit…

Mouais... En anglais ça fait moins méchant...