연속성을 재귀 대체물로 사용할 수 있습니까?

Question

다음 함수는 n = 5,000에 대해 '스택 레벨 (SystemStackError)'을 생성합니다.

def factorial(n)
  n == 0 ? 1 : factorial(n -1) * n
end

Continuations/CallCC를 사용 하여이 오류를 피하는 방법이 있습니까?

메모:

나는 이것이 재귀없이 구현 될 수 있다는 것을 알고 있습니다. 예를 들어

def factorial2(n)
  (1..n).inject(1) {|result, n| result * n } 
end

Answer 1

확신하는. 연속은 무엇이든 할 수 있습니다! 그러나 결국 루프 또는 기능 호출의 두 가지 중 하나를 재창조하게됩니다. 내 컴퓨터에서 기본적으로 꼬리 통화 최적화를 수행하고 Call/CC를 사용한 꼬리 재귀 ~ 아니다 최적화하십시오. 이 프로그램은 각각 신속하게 멍청합니다 callcc 전체 통화 스택을 캡처합니다. 해당 코드는 여기에 Call/CC 루프가 있습니다.

def fact( n )
    (n, f, k) = callcc { |k| [ n, 1, k ] }
    if ( n == 0 ) then return f
    else k.call n-1, n*f, k
    end
end

메모: 이전에는 전화/CC가 연속 통과 체인을 시작하는 것이 아니라 재귀의 필요성에 대해 혼란스러워했기 때문에 아래의 의견을 잊었습니다.

Answer 2

테일 콜 최적화를 활성화 할 수 있습니다 tailcall_optimize :factorial, 가져 왔습니다 여기.

class Class
  def tailcall_optimize( *methods )
    methods.each do |meth|
      org = instance_method( meth )
      define_method( meth ) do |*args|
        if Thread.current[ meth ]
          throw( :recurse, args )
        else
          Thread.current[ meth ] = org.bind( self )
          result = catch( :done ) do
            loop do
              args = catch( :recurse ) do
                throw( :done, Thread.current[ meth ].call( *args ) )
              end
            end
          end
          Thread.current[ meth ] = nil
          result
        end
      end
    end
  end
end

보다 이 흥미로운 게시물 꼬리 재귀가 활성화되어 있는지 결정하는 것.

Answer 3

문제는 함수가 반환된다는 것입니다 factorial(n -1) * n 이것은 표현이며 단일 재귀 호출이 없습니다. 반환 문에서 함수 호출 만있는 경우 기능을 호출합니다. 꼬리 재귀, 좋은 컴파일러 / 통역사 (루비가 가능하는지 확실하지 않음)는 스택 사용을 피하기 위해 약간의 최적화를 수행 할 수 있습니다.

이러한 꼬리 수반 기능은 이와 같이 보일 수 있지만 저는 루비 프로그래머가 아니므로 통역사의 구문이나 기능에 익숙하지 않습니다. 그러나 당신은 스스로 시도 할 수 있습니다.

def factorial(n, result=1)
    n == 0 ? result : factorial(n-1, result * n)
end