What's the right way to implement very deep recursion in Ruby in *clean* way?

Question

Ruby, of course, does have recursion, just like any other high-level programming language. This works fine as long as recursion depth is not too high, but if it is, you will catch a 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 to simply increase the stack size. Unfortunately, answers I found on the subject suggested altering the OS state in one or another way - tinkering with Ruby interpreter source code, ulimit, compile flags and the like - which is beyound pure Ruby and, of course, is not always possible, especially in secure environments. So, the less obvious solutions coming to mind are to rewrite the offending function in a non-recursive way or reimplement a 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 not too complex functions in this way can be a tedious task, and the resulting code seems to be too cluttered and obscured in comparsion to original one. I wanted to involve some metaprogramming and write some sort of a "wrapper", which could make the wrapped function behave properly with deep recursion while being clean enough, even if not looking exactly as unwrapped one would. I implemented a solution with Fibers, which initially seemed good enough, but then I encountered some unexpected difficulties (see the related question for details).

So, I'm looking for a right and clean - with as least cluttering and obscuring as possible - way to implement very deep recursion calls without hurting the performance too much.

Answer 1

I came up with this solution. It is still far from perfect, but seem to be good enough in the absence of better ideas. It basically splits the function in the point of recursive call and postpones any calculations that need to be done after with 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

Usage:

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 reimplementation of the call stack, but looks much cleaner. And if no post-rcall calculations are required, it looks even better, similar to that of 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 produce 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 a quick as the equivalent iterative method.

For a meta-programming solution that optimizes a tail-recursive function, please see Tail Call Optimization in Ruby. The key to pulling this trick off is obtaining the source of the method using method_source.