延续可以用来替代递归吗？

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

注意： 之前我忘记了 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 ，这是一个表达式，而不是单个递归调用。如果你设法在 return 语句中只包含函数调用，那么该函数被称为尾递归，并且一个好的编译器/解释器（我不确定 Ruby 是否有能力）可以做一些事情优化以避免堆栈的使用。

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

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