What is the right way to implement very deep recursion in Ruby * pure *?

Question

Ruby, of course, has recursion, like any other high-level programming language. This works fine until the recursion depth is too high, but if so, you will catch the stack overflow:

#!/usr/bin/ruby2.0 def rec_naive(i) return 1 if i==1 rec_naive(i-1) + i end puts rec_naive(10000) #(Stack size: ~9360) #==> test.rb:3: stack level too deep (SystemStackError) 

The most obvious solution that comes to mind is simply to increase the size of the stack. Unfortunately, the answers that I found on the topic are suggested by changing the state of the OS in one way or another - redoing the source code of the Ruby interpreter, ulimit , compiling flags, etc., which is pure Ruby and, of course, is not always possible, especially in protected environments . Thus, the less obvious solutions that come to mind are to rewrite the violation function in a non-recursive way or override the calling stack:

 # Recursion-free way def rec_norecurse(i) acc = 0 (1..i).each do |n| acc += n end return acc end puts rec_norecurse(100) # Reimplementing the call stack StackFrame = 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 lastresult end customstack = [StackFrame.new(:entrance_point, [100])] puts rec_customstack(customstack) 

However, rewriting even less complex functions in this way can be a tedious task, and the resulting code seems too cluttered and obscured compared to the original. I wanted to use some metaprogramming and write some kind of “wrapper” that could make the wrapped function behave correctly with deep recursion, being clean enough even if it didn't look exactly like it was unfolding. I implemented a solution with Fibers, which initially seemed pretty good, but then I ran into some unexpected difficulties ( see Related question for details).

So, I'm looking for the right and clean - with as little clutter and shadowing as possible - a way to realize very deep recursive calls without damaging the performance too much.

Answer 1

I came up with this solution. He is still far from perfect, but apparently good enough in the absence of better ideas. It basically separates the function at the recursive call point and defers any calculations that need to be done after the blocks:

 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 result end 

Using:

 puts (rcall 100 do |rcaller, i| if i==1 1 else rcaller.(i-1) {|i2| i2+i } end end) # ==> 5050 

This is even slower than reimplementing the call stack, but it looks a lot cleaner. And if no post-rcall calculations are required, it looks even better, like a simple tail call -

 puts (rcall(100, []) do |rcaller, i, acc| if i==1 [1, *acc] else rcaller.(i-1, [i, *acc]) end end).join', ' #==> 1, 2, 3..., 99, 100 

Answer 2

Another option is to use tail call optimization to allow the compiler to create iterative code rather than pushing methods and arguments on the stack:

 RubyVM::InstructionSequence.compile_option = { tailcall_optimization: true, trace_instruction: false } RubyVM::InstructionSequence.new(<<-EOF).eval def sum_down(n, acc=1) return acc if n == 1 return sum_down(n-1, n+acc) end EOF puts sum_down(100) # => 5050 puts sum_down(100000) # => 5000050000 

This method is resistant to stack overflow and should be fast as an equivalent iterative method.

To solve metaprogramming that optimizes the tail recursion function, see Tail Call Optimization in Ruby . The key to extracting this trick is getting the method source using method_source .