"Stack level too deep" with Ackermann-function in Ruby

5
votes

I'm using Ruby v1.9.1 to write a program with the Ackermann-function for my class in University. The code is the following:

def ackermann(n,m)
  if n == 0 && m > 0
    return m+1
  elsif n > 0 && m == 0
    return ackermann(n-1,1)
  elsif n > 0 && m > 00
    return ackermann(n-1,ackermann(n,m-1))
  else
    puts "Wrong input, m and n must be higher than 0"
  end
end

puts ackermann(5,5)

This is a highly recursive function. So I get the error "stack level too deep (SystemStackError)". Is there any way or workaround to fix this error?

3
rubystack
Related, not sure if exactly a duplicate: stackoverflow.com/questions/242617/… - millimoose
Also, there's the possibility that A(5,5) just isn't feasible to compute with today's computers at all. - millimoose
side node: don't put a explicit return, it's not idiomatic. Also, raise an exception on the else instead of just printing the error. - tokland
The stack overflow just might be the lesson, rather than a problem to solve. - outis
@Inerdia I'd like to see how many TB of RAM GMP will use up if you use gmp's bigints for ackermann memoization and run A(5,5) - moshbear

3 Answers

2
votes

You can rewrite it to a non-recursive function so it doesn't run out of stack space, but it's totally pointless.

Take a look at the range of those values.

1
votes

Memoize recursive calls. Make a map of { [int, hyperlong] => hyperlong }s to use a dynamic programming approach to running out of stack space.

Here is a C++ example: http://pastebin.com/tVQ7yB31

Known bugs: ack(3, 10) uses up over 3 GB of heap memory.

0
votes

Tail-recursive algorithms (I am afraid the 6th line in your algorithm makes it not tail-recursive, though) may use TCO (Tail call optimization). To enable it in Ruby 1.9:

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

According to LtU guys, the algorithm can be written as tail-recursive:

http://lambda-the-ultimate.org/node/2673