Why do I get "stack level too deep" with recursion?

Question

I have this ruby code:

def get_sum n
    return 0 if n<1
  (n%3==0 || n%5==0) ? n+get_sum(n-1) : get_sum(n-1) #continue execution
end 

puts get_sum 999

Seems to be working for values up until 999. When I try 9999 it gives me this:

stack level too deep (SystemStackError)

So, I added this:

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

but nothing happened.

My ruby version is:

ruby 1.9.3p392 (2013-02-22 revision 39386) [x86_64-darwin12.2.1]

I also increased the machine's stack size ulimit -s 32768 which I think is 32MB?

I don't think it is my code's fault as it works with smaller numbers, and I don't think 9999 is a big number. I have 8GB of RAM and I think it is more than enough. Any ideas/help?

Answer 1

Your method cannot take advantage of tail-call optimization (TCO) because it's not tail-recursive, the last expression of the method should be a call to the method itself, get_sum. So there is nothing wrong, simply you reached the recursion limit. With Ruby 1.9.3, that limit is:

def recursive(x)
  puts(x)
  recursive(x+1)
end

recursive(0)
...
8731

This method, on the other hand, is tail-recursive:

def self.get_sum_tc(n, acc = 0)
  if n < 1
    acc
  else
    get_sum_tc(n - 1, acc + ((n % 3 == 0 || n % 5 == 0) ? n : 0))
  end
end 

Your Ruby may or may not support it. In Ruby you can use recursion when you have some certainties about the depth-level you'll reach, but it's definitely not idiomatic to loop over a collection of unknown size. You usually have other abstractions for this kind of tasks, for example:

(1..9999).select { |x| x % 5 == 0 || x % 3 == 0 }.reduce(0, :+)

Answer 2

The problem is, you have a routine n+get_sum(n-1), when n has common factors 3 or 5, Ruby goes ahead to this routine. This cannot be optimized by tail-recursion. Ruby has to keep the current frame to remember the current n and only when get_sum(n-1) is computed can Ruby return and throw away the frame.

Generally, the stack space is expensive. The operating system reserves about 2M (maybe a bit more) stack space for each process. This can be consumed up quickly. For your code, (9999/3 + 9999/5) recursive calls consumed all the stack space.

If you want to keep the recursive programming pattern, you have to change the behavior of your method call from recursive (your current state) to iterative.

def get_sum(n, sum = 0)
  return sum if n < 1
  if n % 3 == 0 || n % 5 == 0
    get_sum(n - 1, sum + n)
  else
    get_sum(n - 1, sum)
  end
end

However, it seems that Ruby's tail recursion optimization isn't that powerful. For the above code sample, there are two different get_sum() tail calls. Ruby won't optimize this. You'll have to rewrite the two calls into one.

And besides, to make this work with the RubyVM tweak you have provided, you have to load the method definition at runtime. That's because the RubyVM tweak happens at runtime. You can't put the method definition directly in the same file, or the method will be parsed at compile time and no optimization will take effect.

You can either put the get_sum in a separate file and require that lib after the RubyVM tweak:

# file: test_lib.rb
def get_sum(n, sum = 0)
  if n < 1
    sum
  else
    get_sum(n - 1, sum + (n % 3 == 0 || n % 5 == 0 ? n : 0))
  end
end
# eof

# file: test.rb
RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

require_relative 'test_lib'

puts get_sum(999999)

Or, use eval to evaluate the method definition in a String at runtime:

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

eval <<END
  def get_sum(n, sum = 0)
    if n < 1
      sum
    else
      get_sum(n - 1, sum + (n % 3 == 0 || n % 5 == 0 ? n : 0))
    end
  end
END

puts get_sum(990000)