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

ruby

Solution

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, :+)

Problem

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?

Original source