可以使用continuations作为递归的替代吗？

下面的函数生成n的“层叠级别过深（SystemStackError）” = 5000可以使用continuations作为递归的替代吗？

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

来源

2010-03-17 Sam

您不需要参数注入，它默认为它被调用的Enumerable的第一个元素。还有一个Ruby支持Symbol＃to_proc（1.8.7+，1.8.6 + Facets），你可以这样写factorial2：（1..n）.inject（＆：*） – 2010-03-17 09:16:07

当然。继续可以做任何事情！但是，最终你会重新做出以下两件事之一：循环或函数调用。在默认情况下进行尾部优化优化的机器上，使用call/cc进行尾递归，不是得到优化。该程序迅速陷入瘫痪，因为每个callcc显然都捕获了整个调用堆栈。该代码被打破，这里是一个呼叫/ 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的不只是一个开始延续传递链，得到了困惑的需要递归，因此下面的评论。

来源

2010-03-17 01:35:51 Potatoswatter

或者更好的是，不要使用递归来解析阶乘。这根本没有意义。 – 2010-03-17 01:43:54

@比利：确实。但在尝试任何新的控制流构造时，这是一个很好的模型问题。 – Potatoswatter 2010-03-17 01:51:02

我发现n = 10,000时注射速度更快，但n = 100,000时更快。 – Sam 2010-03-17 05:56:51

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

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

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

来源

2010-03-17 00:34:12 tux21b

你的例子生成相同的错误。 – Sam 2010-03-17 00:40:10

好的，Ruby不会（总是）进行尾部调用优化。所以，在一些ruby实现这个代码可能工作，并在其他人不...看到这里：http://stackoverflow.com/questions/824562/does-ruby-perform-tail-call-optimization – tux21b 2010-03-17 00:45:51

这取决于编译器/ intepreter。 Ruby不保证tail-call优化，因为MRI Ruby本身不是尾递归的。像MacRuby这样的实现应该可以做到。 – Chuck 2010-03-17 00:47:54

你能使用tailcall_optimize :factorial尾调用优化，从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

请参阅this interesting post关于确定是否启用尾递归。

来源

2010-03-17 00:38:23 JRL

每次我认为我已经“看过大象”时，Ruby的片段就会出现，这让我感觉和最新的招聘一样绿。 – 2010-03-17 05:18:12

该解决方案对我无效。请发布完整的解决方案。 – Sam 2010-03-19 02:38:33

我似乎无法得到这个格式很好，所以这里是在丑陋的文字。类事实 DEF事实（N，ACC）如果n == 1 ACC 别的事实（N-1，N * ACC）端端 tailcall_optimize：事实 DEF阶乘（正）事实上（n，1）结束结束 – 2010-08-02 04:18:07

可以使用continuations作为递归的替代吗？

回答

相关问题