Можно ли использовать продолжения вместо рекурсии?

Question

Следующая функция генерирует «слишком глубокий уровень стека (SystemStackError)» для n = 5000.

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

Есть ли способ избежать этой ошибки, используя continues/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

Примечание: ранее я забыл, что call/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 это выражение, а не одиночный рекурсивный вызов.Если вам удается иметь только вызов функции в операторе возврата, то функция вызывается хвостовая рекурсия, а хороший компилятор/интерпретатор (я не уверен, способен ли Ruby на это) может выполнить некоторые оптимизации, чтобы избежать использования стека.

Такая функция хвостовой рекурсии может выглядеть так, но обратите внимание, что я не программист Ruby, поэтому я не привык ни к синтаксису, ни к возможностям интерпретатора.Но вы можете попробовать это самостоятельно:

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