ackermann函数用递归和非递归两种方法实现.cpp

Ackermann for Data Structure

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

long Ackermann(long,long);


int main()
{
	while(1)
	{
		long a,b;
	    cout << "m=?";
	    cin >> a;
	    cout << "n=?";
	    cin >>b;
	    cout << Ackermann(a,b) << endl;
	}
	return 0;
	
}


long Ackermann(long m,long n)
/*{
     if(m==0)
		 return n+1;
	 else
	 {
		 if(n==0)
			 return Ackermann(m-1,1);
		 else
			 return Ackermann(m-1,Ackermann(m,n-1));
	 }
}//递归算法
*/
{
	long stack[10000];
    int pos=1;
    stack[0]=m;
	stack[1]=n;
    while(pos)
    {       
		n=stack[pos--];
        m=stack[pos]; 
		if(m==0) 
			stack[pos]=n+1; 
		if(m!=0 && n==0) 
        {            
			stack[pos++]=m-1; 
			stack[pos]=1;     
		}        
		if(m!=0 && n!=0)   
		{           
			stack[pos++]=m-1;
            stack[pos++]=m; 
			stack[pos]=n-1;    
		}   
	}   
	return stack[0];
}//非递归算法