可以继续使用continuation作为递归的替代吗？

Question

以下函数为n = 5,000生成"堆栈级别太深(SystemStackError)"

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

有没有办法使用continuation/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不只是启动一个连续传递链并且对递归的需要感到困惑,因此下面的注释.