0

What is wrong in my code? It doesn't return the correct answer,

#include <iostream>
using namespace std;

int ack(int m, int n)
{
    if (m == 0) return n + 1;

    if(n == 0) return ack(m - 1, 1);

    return ack(m - 1, ack(m, n - 1));

}

int main()
{
    cout << ack(4, 1) << endl;
    return 0;
}

Here is the output:

enter image description here

Thanks.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
User_67128
  • 1,230
  • 8
  • 21
  • StackOverflow - your recursion goes too deep I would guess. – Ted Lyngmo Sep 21 '20 at 20:18
  • I believe so but someone was able to find the value in his computer with the same program, I'm wondering is there anything with my ide setup, I'm using code::blocks. Machine has 8GB ram. @Ted Lyngmo – User_67128 Sep 21 '20 at 20:23
  • I think that you _may_ be successful if you compile with max optimization turned on so that you get tail recursion in the assembly code. Is the answer supposed to be 65533? – Ted Lyngmo Sep 21 '20 at 20:25
  • 1
    I rewrote it [without recursion](https://godbolt.org/z/rEGfq5). It becomes a bit slow but shouldn't crash. It's too slow to run on godbolt so you'll have to try it on your machine. Be sure you turn on max optimization. – Ted Lyngmo Sep 21 '20 at 20:54
  • I solved it with a combination of recursion and some memorization. But curious why it is not working in my computer. Basically I work on java -eclipse, do not know a lot about code::blocks. Thanks. – User_67128 Sep 21 '20 at 20:57
  • I would guess that it doesn't optimize the code well so that it actually does deep recursion and your stack can't handle it. Did you try with max optimization? – Ted Lyngmo Sep 21 '20 at 21:00
  • Where to set optimization, please? – User_67128 Sep 21 '20 at 21:01
  • 1
    No idea. I've never used Code::Blocks. `-O3` is common if you have a `gcc` or `clang` based compiler. I would however not trust optimization to solve this since it may not be able to handle all inputs you throw at the function. If the values are known at compile time it may be very successful, but not if the values are given at runtime. – Ted Lyngmo Sep 21 '20 at 21:02
  • 1
    It works, Thanks a lot. :) – User_67128 Sep 21 '20 at 21:08
  • Memoize it!! That will make it both faster and use less memory https://stackoverflow.com/questions/12753979/c-memoization-understanding – Jeffrey Sep 21 '20 at 21:08
  • Yeah, I knew that, but I am interested for recursion. @Jeffrey. – User_67128 Sep 21 '20 at 21:10
  • 1
    You can use memoization and recursion at the same time. – cigien Sep 21 '20 at 21:26
  • How to add compiler flags on Code::Blocks https://stackoverflow.com/questions/33208733/how-to-add-compiler-flags-on-codeblocks – Jerry Jeremiah Sep 21 '20 at 22:35

1 Answers1

1

Compiling it with a C compiler, instead of C++, your ack() function returned correctly, 65533, for me in about 20 seconds.

Using a recursive algorithm from RosettaCode that isn't doubly recursive like yours, returns the correct value in about 10 seconds:

int ack(int m, int n)
{
    for (; m > 0; m--) {
        n = (n == 0) ? 1 : ack(m, n - 1);
    }

    return n + 1;
}

Since you're not going to reach higher Ackermann values with this code, I don't see the point in going much faster.

cdlane
  • 40,441
  • 5
  • 32
  • 81