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 :

• Récursion terminale
• La récursivité, par bluestorm
• Scheme