Geek asks and answers

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

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

It seems to work for values ​​up to 999. When I try 9999, it gives me the following:

stack level too deep (SystemStackError)

So, I added the following:

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

but nothing happened.

My ruby ​​version:

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

I also increased the stack size of the machine ulimit -s 32768, which in my opinion is 32 MB?

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

+5
source share
2 answers

" " (TCO), tail-recursive, , get_sum. , , . Ruby 1.9.3 :

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

recursive(0)
...
8731

, , :

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

Ruby . Ruby , , , , . , :

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

, n+get_sum(n-1), n 3 5, Ruby . . Ruby , n, get_sum(n-1) , Ruby .

, . 2 (, ) . . (9999/3 + 9999/5) .

, ( ) .

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

, , Ruby . get_sum(). Ruby . .

, RubyVM , , . , RubyVM . , , .

get_sum require, lib RubyVM:

# 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)

eval String :

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)
+4

More articles:


All Articles