遞迴函式

讓我們從一個簡單的演算法開始，看看如何在 Ruby 中實現遞迴。

麵包店有產品可供出售。產品是包裝。它僅以包裝為訂單提供服務。包裝從最大包裝尺寸開始，然後剩餘數量由下一包裝尺寸填充。

例如，如果收到 16 的訂單，麵包店從 5 包中分配 2，從 3 包中分配 2。2 5 + 2 3 = 16.讓我們看看這是如何在遞迴中實現的。allocate 是這裡的遞迴函式。

#!/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}"

輸出是：

包組合是：[3,3,5,5]