[ SCR ] Ackermann sample with memoization technique

ackermann.cpp

#include <iostream>
#include <cstdlib>
#include <cstring>

#define MAX_M 10
#define MAX_N 1000000
#define VERBOSE false

// ------------------------------------------------------------
// Ackermann sample with memoization technique for optimization
// ------------------------------------------------------------

using namespace std;

int res[MAX_M][MAX_N];
long long calls = 0;
long long peakM = 0;
long long peakN = 0;
bool warned = false;

int ack(int m, int n) {

    if(!warned && (m > MAX_M-1 || n > MAX_N-1)) {
        // the space allocated is not enough for memoization, fall back to recursion
        warned = true;
        cout << "\n\t:: YOU SHOULD INCREASE MAX_M OR MAX_N TO GET CORRECT RESULTS ::\n\n";
    }
    // memoization: return if previously calculated
    else if(res[m][n] != -1) return res[m][n];

    if(VERBOSE){
        calls++;
        if(peakM < m) peakM = m;
        if(peakN < n) peakN = n;
    }

    int ans;

    if (m == 0)
        ans = n + 1;
    else if (n == 0)
        ans = ack(m - 1, 1);
    else
        ans = ack(m - 1, ack(m, n - 1));

    res[m][n] = ans;        // save result
    return ans;
}

int main(int argc, char **argv) {

    // set whole memoization matrix to -1
    memset(res, -1, sizeof(res[0][0]) * MAX_M * MAX_N);

    int i, j;
    for (i = 0; i < 6; i++) {
        for (j = 0; j < 6; j++) {
            cout << "Ackermann(" << i << "," << j << ") = " << ack(i,j) << "\n";
            if (VERBOSE) {
                cout << "\t" << calls << " calls, with max M=" << peakM << " and N=" << peakN << "\n\n";
                calls = 0;
            }
        }
    }

}