#!/usr/bin/ruby2.0def rec_naive(i) return 1 if i==1 rec_naive(i-1) + iendputs rec_naive(10000) #(Stack size: ~9360)#==> test.rb:3: stack level too deep (SystemStackerror)
想到的最明显的解决方案是简单地增加堆栈大小.不幸的是,我在主题上发现的答案suggested以一种或另一种方式改变 *** 作系统状态 – 修改Ruby解释器源代码,ulimit,编译标志等 – 这是纯粹的Ruby,当然,并不总是可行的,尤其是在安全的环境中.因此,想到的不太明显的解决方案是以非递归方式重写违规函数或重新实现调用堆栈:
# Recursion-free waydef rec_norecurse(i) acc = 0 (1..i).each do |n| acc += n end return accendputs rec_norecurse(100)# Reimplementing the call stackStackFrame = Struct.new(:state,:args)def rec_customstack(stack) lastresult = nil until stack.empty? frame = stack.last state,args = frame.state,frame.args i = args[0] case state when :entrance_point if i==1 #-- return 1 #-- lastresult = 1 stack.pop #--------------- else #-- rec(i-1) #-- stack.last.state = :returned_from_recursion stack << StackFrame.new(:entrance_point,[i-1]) #--------------- end when :returned_from_recursion #-- return rec_result+i #-- lastresult = lastresult + i stack.pop #-------------------------- end end return lastresultendcustomstack = [StackFrame.new(:entrance_point,[100])]puts rec_customstack(customstack)
然而,以这种方式重写甚至不太复杂的函数可能是一项单调乏味的任务,并且所得到的代码似乎过于混乱并且与原始代码相比变得模糊不清.我想要涉及一些元编程并编写某种“包装器”,它可以使包装函数在深度递归时表现正常,同时保持足够干净,即使看起来不像未包装的那样.
我用Fibers实现了一个解决方案,最初似乎已经足够好了,但后来我遇到了一些意想不到的困难(详见see the related question).
所以,我正在寻找一个正确而干净 – 尽可能减少混乱和模糊 – 实现非常深的递归调用而不会过多损害性能的方法.
解决方法 我想出了这个解决方案.它仍然远非完美,但在没有更好的想法的情况下似乎已经足够好了.它基本上在递归调用时拆分函数,并推迟使用块后需要完成的任何计算:def rcall(*args,&block) cs = [nil] #Call Stack rec = false rcaller = proc do |*pargs,&pblock| # Enqueue and return control to rcall rec = true # We *are* doing rcall cs << pblock pargs end result = args until cs.empty? rec = false result = block.call(rcaller,*result) while (!rec) && (!cs.empty?) # we got result! Return it to past preproc call and work it :3 lastblock = cs.pop result = lastblock.call(*result) if !lastblock.nil? end end return resultend
用法:
puts (rcall 100 do |rcaller,i| if i==1 1 else rcaller.(i-1) {|i2| i2+i } endend)# ==> 5050
这比调用堆栈的重新实现更慢,但看起来更清晰.如果不需要post-rcall计算,它看起来会更好,类似于简单的尾调用 –
puts (rcall(100,[]) do |rcaller,i,acc| if i==1 [1,*acc] else rcaller.(i-1,[i,*acc]) endend).join','#==> 1,2,3...,99,100总结
以上是内存溢出为你收集整理的以* clean *方式在Ruby中实现非常深度递归的正确方法是什么?全部内容,希望文章能够帮你解决以* clean *方式在Ruby中实现非常深度递归的正确方法是什么?所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)