Efficient Ackermann function

Ackermann is a complex recursive function (I still don't know how this differs from a simple recursive function) that grows really really freaking quickly.

I've implemented a very quick method of calculating the results. It's faster because I noticed a great deal of duplicate function calls, so I put known values into a table & look them up when the values match up.

However, it segfaults for n, m > 4, 1 or 3 14. I was wondering if there's a way to fix this. Obviously I'm running out of memory (can't attach pic here, but valgrind says can't grow the stack) :)

Excuse the shitty code, I'm still learning C++. I know that I should probably have a set of pairs of ints rather than using that stringstream conversion BS. Feel free to suggest some ways to help efficiency =D

Thanks,
Anon.

#include <iostream>
#include <map>
#include <stdlib.h>
#include <stdio.h>
#include <sstream>

using namespace std;

map<string,int> cache;

int ack(int m, int n) {
  string key;
  stringstream ss;
  ss << m << "," << n;
  ss >> key;
  if (cache.find(key) != cache.end()) {
    return(cache[key]);
  }

  int result;
  if (m == 0) {
    cache[key] = n+1;
    return n+1;
  }
  else if (n == 0) {
    result = ack(m-1, 1);
    cache[key] = result;
    return result;
  }
  else {
    result = ack(m-1, ack(m, n-1));
    cache[key] = result;
    return result;
  }
}

int main() {
  int a, b;
  cout << "Enter a and b, ( <0 || <0 ) to quit \n";
  cin >> a >> b;
  while (a > 0 && b > 0) {
    cout << "Ack is: " << ack(a, b) << endl;
    cin >> a >> b;
  }
}

Enjoy your integer overflows.

Also, use dynamic programming.

Oh yeah, right, ints.

Should've been GMP extended ints i spose.

What's dynamic programming ?

var ack_cache:Array=new Array();

function ack(m:int,n:int):int{
 var a:int;
 if(ack_cache[m,n]){
  return ack_cache[m,n];
 }
 if(m){
  if(n){
   a=ack(m-1,ack(m,n-1));
  }else{
   a=ack(m-1,1);
  }
 }else{
  a=n+1;
 }
 ack_cache[m,n]=a;
 return a;
}

SPOILER: The Ackermann function is useless.

>>2
fail

int ackermann(int m, int n) {
   if (m == 0)
     return n+1;
   else if (n == 0)
     return ackermann(m-1, 1);
   else
     return ackermann(m-1, ackermann(m, n-1));
 }

>6
too bad your function is slow as fuck
>>5
NO U

This is exactly like a naive recursive fib function is it not.

Ackermann sounds like a Jew function.  BBcode doesn't support it, so it's probably useless as well.

>>1
you should probably use a pair of ints rather than using that stringstream conversion BS.  or just create a 2d lookup table and get rid of most of your overhead.

>>10
see >>4

you all should read sicp. automemoization ftw

old thread is old