Implement the ackermann function using recursive calls
Use memoization with hash maps to speed up recursive calls
Use memoization with a map data structure to speed up evaluation of the Ackermann function. As a reminder, the definition is as follows:
Fill in the code below to compute this function using recursive calls. Memoization on the first two cases has already been provided for you, but you'll need to use memoization for the third case. Note that there are actually two functions to memoize; the inside and the outside one.
Student Code
#include <stdio.h>
#include <map>
#include <string>
#include <sstream>
using namespace std;
/**
* @brief Return a unique string key "m_n" to go
* with an ackermann input (m, n)
*
* @param m First input to ackermann function
* @param n Second input to ackermann function
* @return string Key to use
*/
string getKey(int m, int n) {
stringstream stream;
stream << m << "_" << n;
return stream.str();
}
/**
* @brief
*
* @param m First input to ackermann function
* @param n Second input to ackermann function
* @param count Reference to variable holding number of calls made to A
* @param memory A map whose key is a string representation "m_n"
* and whose value is A(m, n)
* @return int The ackermann function A(m, n)
*/
int A(int m, int n, int* count, map<string, int>& memory) {
(*count)++;
string s = getKey(m, n);
int res = 0;
if (memory.find(s) != memory.end()) {
res = memory[s];
}
else {
if (m == 0) {
res = n+1;
memory.insert(pair<string, int>(s, res));
}
else if (n == 0) {
res = A(m-1, 1, count, memory);
memory.insert(pair<string, int>(s, res));
}
else {
// TODO: Fill this in
}
}
return res;
}
Main Area
int main() {
int count = 0;
map<string, int> memory;
int res = A(2, 2, &count, memory);
printf("%i (%i). ", res, count);
memory.clear();
res = A(3, 3, &count, memory);
printf("%i (%i).", res, count);
memory.clear();
res = A(3, 4, &count, memory);
printf("%i (%i).", res, count);
printf("\n");
}
Compiler Feedback
Program Output
Click compile to compile your code. If it succeeds with no syntax errors, then click run to run your code. If it passes the tests, it will automatically submit to Canvas and send you an e-mail. You must be connected to the Ursinus Network for submission to be successful! You will receive a copy of your code via e-mail, so you'll know that it was submitted if you receive that e-mail! Please Enter your Ursinus netid before clicking run. This is not your ID number or your email. For example, my netid is ctralie (non Ursinus students can simply enter their name to get this to run, but they won't get an e-mail record or any form of credit)
