Могут ли продолжения использоваться в качестве замены рекурсии? - PullRequest
Новая
       19

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

4 голосов
/ 17 марта 2010

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

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

Есть ли способ избежать этой ошибки с помощью продолжений / callcc?

Примечание:

Я знаю, что это можно реализовать без рекурсии. например, 

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

Ответы [ 3 ]

5 голосов
/ 17 марта 2010

Конечно. Продолжения могут сделать что угодно! Тем не менее, вы в конечном итоге заново изобрели одну из двух вещей: цикл или вызов функции. На моей машине, которая выполняет оптимизацию хвостового вызова по умолчанию, хвостовая рекурсия с вызовом / 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 - это не просто инициализация цепочки прохождения продолжения, и запутался в необходимости рекурсии.

1 голос
/ 17 марта 2010

Вы можете включить оптимизацию хвостового вызова с помощью 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

См. этот интересный пост об определении, включена ли хвостовая рекурсия.

0 голосов
/ 17 марта 2010

Проблема в том, что функция возвращает factorial(n -1) * n, которое является выражением, а не одним рекурсивным вызовом. Если вам удается иметь только вызов функции в операторе return, то функция называется tail recursive , и хороший компилятор / интерпретатор (я не уверен, что Ruby способен на это) может выполнить некоторую оптимизацию чтобы избежать использования стека.

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

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