递归函数

让我们从一个简单的算法开始,看看如何在 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]