Ruby Language Récursion de la queue


Exemple

De nombreux algorithmes récursifs peuvent être exprimés en utilisant une itération. Par exemple, la plus grande fonction de dénominateur commun peut être écrite récursivement :

def gdc (x, y)
  return x if y == 0
  return gdc(y, x%y)
end

ou itérativement:

def gdc_iter (x, y)
  while y != 0 do
    x, y = y, x%y
  end

  return x
end

Les deux algorithmes sont équivalents en théorie, mais la version récursive risque de générer une erreur SystemStackError . Cependant, comme la méthode récursive se termine par un appel à elle-même, elle pourrait être optimisée pour éviter un débordement de pile. Une autre façon de le dire: l'algorithme récursif peut générer le même code machine que l'itératif si le compilateur sait rechercher l'appel à la méthode récursive à la fin de la méthode. Ruby ne fait pas l’optimisation des appels de queue par défaut, mais vous pouvez l’ activer avec :

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

Outre l’activation de l’optimisation des appels, vous devez également désactiver le suivi des instructions. Malheureusement, ces options ne s'appliquent qu'au moment de la compilation, vous devez donc soit require la méthode récursive à partir d'un autre fichier, soit eval la définition de la méthode:

RubyVM::InstructionSequence.new(<<-EOF).eval
  def me_myself_and_i
    me_myself_and_i
  end
EOF
me_myself_and_i # Infinite loop, not stack overflow

Enfin, l'appel de retour final doit renvoyer la méthode et uniquement la méthode . Cela signifie que vous devrez réécrire la fonction factorielle standard:

def fact(x)
  return 1 if x <= 1
  return x*fact(x-1)
end

À quelque chose comme:

 def fact(x, acc=1)
   return acc if x <= 1
   return fact(x-1, x*acc)
 end

Cette version transmet la somme accumulée via un second argument (optionnel) par défaut 1.

Lectures complémentaires: Optimisation de l'appel de queue dans Ruby et Tailin 'Ruby .