Ruby Language Recursion in Ruby Recursive function
Example
Let's start with a simple algorithm to see how recursion could be implemented in Ruby.
A bakery has products to sell. Products are in packs. It services orders in packs only. Packaging starts from the largest pack size and then the remaining quantities are filled by next pack sizes available.
For e.g. If an order of 16 is received, bakery allocates 2 from 5 pack and 2 from 3 pack. 25+23 = 16. Let's see how this is implemented in recursion. "allocate" is the recursive function here.
#!/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}"
Output is:
Pack combination is: [3, 3, 5, 5]
