Programming Forums - Ackerman's function

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - Ackerman's function - crash upon launch (http://www.programmingforums.org/showthread.php?t=11595)

Ackerman's function - crash upon launch

This is a simple program that evaluates ackerman's function given 2 values. It opens and closes extremely quickly, no doubt a crash. Can anyone see the problem?

#include <iostream>

#include <cstdlib>

using namespace std; 



int A(int, int);



int A(int in_m, int in_n)

{

        int m = in_m;

        int n = in_n;

        

        if( m == 0 && n >= 0)

        {

            return (A(n + 1,0), 0);

        }

        else if(m>0 && n == 0)

        {

             return (A(m-1, 1));

        }

        else if( m>0 && n>0)

        {

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

        }

}

             



int main()

{

    char ch;

    cout << A(0,0) << endl;

    cout << A(0,9) << endl;

    cout << A(1,8) << endl;

    cout << A(2,2) << endl;

    cout << A(2,0) << endl;

    cout << A(2,3) << endl;

    cout << A(3,2) << endl;

    cout << A(4,0) << endl;



    cin >> ch;

    return 0;



}

Thanks

Running it through a debugger shows a stack overflow.
The last few calls are:

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=1)  Line 22 + 0x10 bytes        C++

         Test.exe!A(int in_m=2, int in_n=0)  Line 18 + 0xe bytes        C++

         Test.exe!A(int in_m=0, int in_n=1)  Line 14 + 0xe bytes        C++

         Test.exe!A(int in_m=1, int in_n=0)  Line 18 + 0xe bytes        C++

You need to change

return (A(n + 1,0), 0);

return n + 1;

Otherwise there is no way out of the function without calling itself again.
Also note that you don't return anything if m or n is less than 0, you should at least return some value, or throw an exception.

OMG.. i'm stupid.. I overthought it..... damn..

Thank you dark...

/*

There's a well known function called the Ackermann function. This function usually appears in computer science courses and texts when the topic of recursion is discussed. The function is defined as:



Use the following function prototype to implement the Ackermann function as a recursive function:



long ack(long,long);



Some values for the Ackermann function are as follows:



    ackerman(0,0)= 0

    ackerman(1,0)= 0

    ackerman(1,1)= 2

    ackerman(1,2)= 4

    ackerman(1,3)= 8

    ackerman(2,1)= 2

    ackerman(2,2)= 4

    ackerman(2,3)= 16

    ackerman(3,1)= 2

    ackerman(3,2)= 4 



The program interaction should look as follows (user inputs are in bold):



Welcome to the Ackermann program.



Enter values for x and y(-1 -1 to exit): 0 0



value is: 0



Enter values for x and y(-1 -1 to exit): 2 3



value is: 16



Enter values for x and y(-1 -1 to exit): -1 -1



Thank you for using the Ackermann program and have a wonderful day.

*/





#include <iostream>

using namespace std;



long ack(long, long);



int main()

{

        long m, n;



        while(1)

        {

                cout<<"Welcome to the Ackermann program.  \n\n"<<endl;

                cout<<"Enter values for x and y(-1 -1 to exit):  \t"<<endl;

                cin>>m>>n;



                if (m== -1 && n== -1)

                {

                        cout<<"Thank you for using the Ackermann program and have a wonderful day."<<endl;

                        break;

                }



                else

                        cout<<ack(m, n)<<"\n\n"<<endl;



        }



        return 0;

}



long ack(long m,long n)

{

        if (m == 0)

                return (2*n);



        if (m >= 1 && n ==0)

                return 0;



        if (m >= 1 && n ==1)

                return 2;



        if (m >= 1 && n >= 2)

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

}

Since we seem to be comparing implementations... from one of my entries to the "500 ways to program 1-10" thread:

unsigned long A(unsigned long m, unsigned long n)

{

  if(!m)

    return n+1;

  if(!n)

    return A(m-1, 1);

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

}

[edit:] As to your code, couple stylistic issues:
- you forward declare the function, then immediately define it. You could take the declaration out.
- you use local variables whose values are just the same as your parameter values. No need for those either.