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

Question

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?

Related, not sure if exactly a duplicate: http://stackoverflow.com/questions/242617/how-to-increase-stack-size-for-a-ruby-app-recursive-app-getting-stack-level-to — millimoose, Nov 05 '11 at 19:18
Also, there's the possibility that A(5,5) just isn't feasible to compute with today's computers at all. — millimoose, Nov 05 '11 at 19:24
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, Nov 05 '11 at 19:25
The stack overflow just might be the lesson, rather than a problem to solve. — outis, Nov 05 '11 at 19:28
@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, Nov 05 '11 at 20:09

score 2 · Answer 1 · answered Nov 05 '11 at 19:21

2

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.

answered Nov 05 '11 at 19:21

Karoly Horvath

94,607
11
117
176

Thanks, you are right. So I will try it with (3,3) and than everything is good ;) – rotespferd Nov 05 '11 at 19:29

moshbear · Accepted Answer · 2011-11-05T20:07:37.637

1

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.

edited Nov 05 '11 at 20:07

answered Nov 05 '11 at 19:31

moshbear

3,282
1
19
33

tokland · Answer 3 · 2011-11-05T19:28:21.683

0

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

edited Nov 05 '11 at 19:28

answered Nov 05 '11 at 19:22

tokland

66,169
13
144
170

Cool! Unforunately, I tried it here using `ruby 1.9.2p180 (2011-02-18 revision 30909) [x86_64-linux]` and it did not solve the problem. The case `ackermann(n-1,ackermann(n,m-1))` can not be reduced to a simple tail recursion. – David Grayson Nov 05 '11 at 19:30
@David: added link to a recursive version (Scheme?). I won't claim I understand it :-) – tokland Nov 05 '11 at 19:32
@tokland: basically it uses a variable (nm) to store a *list* of m values (different notation, in the OP's question that's n), emulating a stack. – Karoly Horvath Nov 05 '11 at 19:41

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

3 Answers3