Ruby Language
Récursion en Ruby

Fonction récursive

Commençons par un algorithme simple pour voir comment la récursion pourrait être implémentée dans Ruby.

Une boulangerie a des produits à vendre. Les produits sont en packs. Il dessert les commandes en packs uniquement. L'emballage commence à partir de la taille de l'emballage la plus grande, puis les quantités restantes sont remplies par les emballages suivants.

Par exemple, si une commande de 16 est reçue, la boulangerie alloue 2 du pack 5 et 2 du pack 3. 2 5 + 2 3 = 16. Voyons comment cela est implémenté en récursivité. "allocate" est la fonction récursive ici.

#!/usr/bin/ruby

class Bakery
  attr_accessor :selected_packs

  def initialize
    @packs = [5,3] # pack sizes 5 and 3
    @selected_packs = []
  end

  def allocate(qty)
    remaining_qty = nil

    # ==============================================
    # packs are allocated in large packs first order
    # to minimize the packaging space
    # ==============================================
    @packs.each do |pack|
      remaining_qty = qty - pack

      if remaining_qty > 0
        ret_val = allocate(remaining_qty)
        if ret_val == 0
          @selected_packs << pack
          remaining_qty = 0
          break
        end
      elsif remaining_qty == 0
        @selected_packs << pack
        break
      end
    end

    remaining_qty
  end
end

bakery = Bakery.new
bakery.allocate(16)
puts "Pack combination is: #{bakery.selected_packs.inspect}"

Le résultat est:

La combinaison de paquets est: [3, 3, 5, 5]

Récursion de la queue

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 .