Ackermann function don't work properly in C++

Question

In my home work of Ackermann function I have solved the problem as following

int main()
{
    int y = ack(4,1);
    cout<<"ans is :::: "<< y;

    getch();
    return 0;
}

int ack(int m, int n)
{
    if(m == 0)
    {
        return n+1; 
    }
    else if(m > 0 && n == 0)
    {
        return ack(m-1,1);  
    }
    else if(m > 0 && n>0)
    {
        int x = ack(m,n-1);
        return ack(m-1,x);
    }
    else 
    {
        cout<< "did not worked properly";
    }   
}

This function works great with low values upto m=3 and n = 10 But when I give m = 4/above or n = 15/above this don't work. I get no out put. Program just exit without any warning or error or result.

Please some body tell me the reason why this is happening and how can I solve this problem.

You get a stack overflow. Computing the Ackermann function recursively leads to **very** deep recursion. Make it print out something on each call to see how deep. — Daniel Fischer, Jun 24 '12 at 13:12

score 7 · Accepted Answer · edited May 23 '17 at 12:23

7

The number (4, 15) is such a big number that is impossible to calculate and represent. Look at the table of values. For example (4, 2) is orders of magnitude bigger than number of particles in the observable universe!

I had a similar homework. The whole point is to show you how insanely something can grow. Humans have problem to grokk exponential growth which is pale in comparison to Ackermann function.

Thinking about big numbers can lead to interesting conclusions. Imagine, you are walking along the road which is 2^2^65536 - 3 meters long (that's ackermann(4, 3)). Assuming that average human body is roughly equal to 1m^3 it has got 10^10^70 quantum states. Going down the road you will meet your doppelgangers - exact doppelgangers on quantum level! So they will have execly same thoughts, same scars, itchy elbow in the same spot. They even going to digest same food. You will meet billions of billions of billions doppelgangers. For me, it's really mind-blowing.

edited May 23 '17 at 12:23

Community

1
1

answered Jun 24 '12 at 13:11

Lukasz Madon

14,664
14
64
108

2

Thanks @lukas. I printed how many times it iterate and i found it was huge just for (3,9). – Jun 24 '12 at 13:33
Humans usually have a good idea how to think of an exponential scale; much better than linear scales. See for example [this](http://www.scientificamerican.com/article.cfm?id=a-natural-log). – rubenvb Jun 24 '12 at 13:51
@rubenvb Log scale, not exponential scale. Related but not equivalent. – Konrad Rudolph Jun 24 '12 at 13:57
@Konrad Same/inverse difference. – rubenvb Jun 24 '12 at 14:04
Has it 2^73 or 2^(2^73) quantum states? 2^73 is not a lot for 1 cubic meter of matter. – usr Jun 24 '12 at 14:13
@rubenvb I don't agree. Moste people do have a problem with exponent. One example http://en.wikipedia.org/wiki/Wheat_and_chessboard_problem An exercise for a reader. How many times you have to fold a piece of paper to reach the moon from earth? – Lukasz Madon Jun 24 '12 at 14:52

Ackermann function don't work properly in C++

1 Answers1