Ruby Language
Rekursion i Ruby

Rekursiv funktion

Låt oss börja med en enkel algoritm för att se hur rekursion kan implementeras i Ruby.

Ett bageri har produkter att sälja. Produkter finns i förpackningar. Den levererar endast beställningar i paket. Förpackningen börjar från den största förpackningsstorleken och sedan fylls de återstående mängderna med nästa tillgängliga förpackningsstorlek.

För t.ex. Om en beställning på 16 tas emot fördelar bageriet 2 från 5 paket och 2 från 3 paket. 2 5 + 2 3 = 16. Låt oss se hur detta implementeras i rekursion. "allokera" är den rekursiva funktionen här.

#!/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 är:

Förpackningskombinationen är: [3, 3, 5, 5]

Rekursion för svans

Många rekursiva algoritmer kan uttryckas med iteration. Till exempel kan den största gemensamma nämnarfunktionen skrivas rekursivt :

def gdc (x, y)
  return x if y == 0
  return gdc(y, x%y)
end

eller iterativt:

def gdc_iter (x, y)
  while y != 0 do
    x, y = y, x%y
  end

  return x
end

De två algoritmerna är likvärdiga i teorin, men den rekursiva versionen riskerar en SystemStackError . Eftersom den rekursiva metoden slutar med ett samtal till sig själv, kan den emellertid optimeras för att undvika ett stacköverskridande. Ett annat sätt att uttrycka det: den rekursiva algoritmen kan resultera i samma maskinkod som iterativet om kompilatorn vet att leta efter rekursiv metodsamtal i slutet av metoden. Ruby utför inte optimering av svanssamtal som standard, men du kan aktivera det med :

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

Förutom att aktivera optimering av svarssamtal måste du också stänga av instruktionsspårning. Tyvärr gäller dessa alternativ endast vid sammanställningstid, så du måste antingen require rekursiv metod från en annan fil eller eval :

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

Slutligen måste det sista retursamtalet returnera metoden och endast metoden . Det betyder att du måste skriva om standardfaktoriell funktion:

def fact(x)
  return 1 if x <= 1
  return x*fact(x-1)
end

Till något som:

 def fact(x, acc=1)
   return acc if x <= 1
   return fact(x-1, x*acc)
 end

Den här versionen överför den ackumulerade summan via ett andra (valfritt) argument som är standard till 1.

Mer information : Tail Call Optimization i Ruby och Tailin 'Ruby .