ruby - 延续可以用作递归的替代品吗？

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显然都捕获了整个调用堆栈。该代码被破坏，这是一个调用/抄送循环：

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

You can enable tail-call optimization with tailcall_optimize :factorial, taken from here.

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

See this interesting post about determining if tail recursion is enabled.

Answer 3

问题是，函数返回factorial(n -1) * n的是一个表达式，而不是单个递归调用。如果您设法在 return 语句中只调用函数，那么该函数称为tail recursive，一个好的编译器/解释器（我不确定 Ruby 是否有能力）可以做一些优化以避免使用堆。

这样的尾递归函数可能看起来像这样，但请注意，我不是 Ruby 程序员，所以我既不习惯语法也不习惯解释器的功能。但是您也许可以自己尝试：

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