Ruby Language Fonction récursive


Exemple

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]