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

发布时间：2020-12-17 02:58:26 所属栏目：百科来源：网络整理

导读：以下函数为n = 5,000生成“堆栈级别太深(SystemStackError)” def factorial(n) n == 0 ? 1 : factorial(n -1) * nend 有没有办法使用continuation / callcc来避免这个错误？注意：我知道这可以在没有递归的情况下实现.例如 def factorial2(n) (1..n).inje

以下函数为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

解决方法

当然.延续可以做任何事情！但是,你最终会重新发明两件事之一：循环或函数调用.在我的机器上,默认情况下进行尾调用优化,使用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不只是启动一个连续传递链并且对递归的需要感到困惑,因此下面的注释.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!