Ruby Language
루비의 재귀

재귀 함수

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]

테일 재귀

많은 재귀 알고리즘은 반복을 사용하여 표현할 수 있습니다. 예를 들어, 가장 큰 공통 분모 함수는 재귀 적 으로 작성할 수 있습니다.

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

또는 반복적으로 :

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

  return x
end

두 알고리즘은 이론적으로는 동일하지만 재귀 버전은 SystemStackError를 위험에 빠뜨 립니다. 그러나 재귀 적 메서드는 자체 호출로 끝나기 때문에 스택 오버플로를 피하기 위해 최적화 할 수 있습니다. 또 다른 방법은 그것을 넣어 : 컴파일러가 메소드의 끝에서 재귀 메서드 호출을 찾기 위해 알고있는 경우 재귀 알고리즘은 반복과 같은 기계 코드가 발생할 수 있습니다. 루비는 기본적으로 꼬리를 호출 최적화를하지 않습니다,하지만 당신은 할 수 와 함께 전원을 켭니다 :

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

꼬리 - 호출 최적화 기능을 켜는 것 외에도 명령 추적 기능을 해제해야합니다. 아쉽게도 이러한 옵션은 컴파일시에만 적용되므로 다른 파일에서 재귀 메서드를 require 하거나 메서드 정의를 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

마지막으로 최종 반환 호출은 메서드와 메서드 만 반환해야합니다. 즉, 표준 계승 함수를 다시 작성해야합니다.

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

무엇인가 :

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

이 버전은 누적 합계를 기본값 인 1 (선택 사항) 인수를 통해 전달합니다.

추가 읽기 : Ruby 및 Tailin 'Ruby의 테일 호출 최적화 .