Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Oct 15th, 2006, 4:47 PM   #1
codylee270
Unverified User
 
Join Date: Sep 2005
Posts: 209
Rep Power: 0 codylee270 is an unknown quantity at this point
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
codylee270 is offline   Reply With Quote
Old Oct 15th, 2006, 7:23 PM   #2
codylee270
Unverified User
 
Join Date: Sep 2005
Posts: 209
Rep Power: 0 codylee270 is an unknown quantity at this point
anyone?
codylee270 is offline   Reply With Quote
Old Oct 15th, 2006, 7:52 PM   #3
The Dark
Programming Guru

 
Join Date: Jun 2005
Posts: 1,627
Rep Power: 11 The Dark will become famous soon enoughThe Dark will become famous soon enough
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++
The Dark is offline   Reply With Quote
Old Oct 15th, 2006, 7:56 PM   #4
The Dark
Programming Guru

 
Join Date: Jun 2005
Posts: 1,627
Rep Power: 11 The Dark will become famous soon enoughThe Dark will become famous soon enough
You need to change
           return (A(n + 1,0), 0);
to
           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.
The Dark is offline   Reply With Quote
Old Oct 15th, 2006, 8:05 PM   #5
codylee270
Unverified User
 
Join Date: Sep 2005
Posts: 209
Rep Power: 0 codylee270 is an unknown quantity at this point
OMG.. i'm stupid.. I overthought it..... damn..

Thank you dark...
codylee270 is offline   Reply With Quote
Old Oct 19th, 2006, 2:07 AM   #6
bl00dninja
Programming Guru
 
bl00dninja's Avatar
 
Join Date: Oct 2004
Location: namespace std
Posts: 1,246
Rep Power: 11 bl00dninja is on a distinguished road
/*
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) ) ) ) );
}
__________________
i put on my robe and wizard hat...

Have you ever heard of Plato, Aristotle, Socrates?...Morons.
bl00dninja is offline   Reply With Quote
Old Oct 19th, 2006, 2:14 AM   #7
Jimbo
Battle Programmer
 
Jimbo's Avatar
 
Join Date: Feb 2006
Location: Bellevue, WA, USA
Posts: 887
Rep Power: 9 Jimbo is on a distinguished road
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.
__________________
<insert disclaimer here>

Last edited by Jimbo; Oct 19th, 2006 at 2:27 AM.
Jimbo is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Combining languages titaniumdecoy Other Programming Languages 12 Jul 13th, 2006 2:03 PM
Compiling Maverik 6.2 (from C) megamind5005 C 16 May 3rd, 2006 5:41 PM
libraries matko C 1 Jan 22nd, 2006 2:12 PM
Jackpot game zorin Visual Basic 3 Jun 10th, 2005 1:19 PM
airport Log program using 3D linked List : problem reading from file gemini_shooter C++ 0 Mar 2nd, 2005 4:12 PM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 11:10 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC