Iterative implementation of the Ackermann function [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review.

Closed 5 years ago.

Improve this question

Here's an iterative implementation of the Ackermann function for review:

#include <stack>
#include <iostream>
#include <tuple>
#include <vector>
int Ackermann(int m, int n) {
 std::stack<int> s;
 s.push(m);
 while (!s.empty()) {
 m = s.top();
 s.pop();
 if (m == 0 || n == 0)
 n += m + 1;
 else {
 s.push(m - 1);
 s.push(m);
 n--;
 }
 }
 return n;
}
int main() {
 std::vector<std::tuple<int, int, int>> tests{
 { 0, 0, 1},
 { 1, 0, 2},
 { 1, 1, 3},
 { 2, 1, 5}
 };
 for (auto const &test : tests) {
 using std::get;
 auto result = Ackermann(get<0>(test), get<1>(test));
 if (result == get<2>(test)) {
 std::cout << "Ackermann(" 
 << get<0>(test) << ", " 
 << get<1>(test) << ") == " 
 << result << ": passed\n";
 }
 else {
 std::cerr << "Error: Ackermann(" 
 << get<0>(test) << ", " 
 << get<1>(test) 
 << ": expected" << get<2>(test) 
 << ", but got: " << result << "\n";
 }
 }
}

Any comments appreciated.

• Kache: acker(3, 1) should return 13. Doesn't this return 11?
• lumpigerAffe: It is not working. e.g. Ackerman(3,0) = 5. Yours does give back 4.

Answer 1

The results of the Ackermann function can grow quite large. An int is only guaranteed to cover up to 32767.

A two-dimensional memorization table would probably be worthwhile.

• Jerry Coffin: "can grow quite large". You sir, have mastered the art of understatement! :-)