Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Nonrecursive algorithm of ackermann function

Posted on 2003-03-24
Medium Priority
3,224 Views
Hi!Experts:
My teacher give me a algorithm about Ackermann function of nonrecursive:
int Ackermann(int m,int n) //Pseudocode
{
Initialize stack1 and stack2;
push m and n into stack1;
do{
pop n and m from stack1;
if(n is a special symbol) n=pop from stack2;
if(m=0) push (n+1) onto stack2;

else if(n=0)
push m-1 and 1 onto stack1;
else{
push m-1 and special symbol onto stack1;
push m and n-1 onto stack1;
}
}while(stack1 is not empty);
result = pop from stack2;
return result;
}
(1)Initizlize stack1 and stack2;
stack1:
stack2:
Q:What's mean of "initialize"?
(2)push m and n into stack1:
stack1:m n
stack2:
(3)pop n and m from stack1:
stack1:
stack2:
(4)if(n is a special symbol) n=pop from stack2;
Q:What's mean of "special symbol"?
...
How to implement?
Is there else nonrecursive algorithm of ackermann function?
3Q!!
0
Question by:TKD
• 3
• 2

Expert Comment

ID: 8195831
**** down,and think...
0

LVL 11

Accepted Solution

dimitry earned 360 total points
ID: 8199060
Short theory: Recursive program can be converted to
non-recursive with pretty well-defined algorithm using stack.
Now, in case of recursive program it will be called exactly in special order and will take from stack whatever it needs to take. In case of non-recursive, especially in your case when you have 2 stacks, program needs to "know" when to switch from stack to stack, etc... For this purpose you can use special data in the stack that defines "end of round", "end of valid data", etc...

0

Author Comment

ID: 8199962
Hi.dimitry:
Could you give me some simple program about that recursive program can be converted to non-recursive with pretty well-defined algorithm using stack? I really don't know how to implement.Could someone give me some hint?Thanks!!
0

LVL 11

Expert Comment

ID: 8200395
I learned this algorithm 10 years ago and don't remember details. :) But the idea is next:
Let's take factorial algorithm:
---------------------------------------------------------
long fact( int n )
{
if( n == 0 ) return( 1L );
return( n * fact(n-1) );
}
void main( void )
{
printf("Factorial of 10 = %ld\n", fact(10));
}
---------------------------------------------------------
long fact()
{
long f;
int n;
while( 1 ) {
n = pop();
if( n == 0 )
return( f );
f *= n;
push( (n - 1) );
}
}
void main( void )
{
push( 10 );
printf("Factorial of 10 = %ld\n", fact());
}
---------------------------------------------------------
Note: You need to implement stack push and pop...
0

Author Comment

ID: 8210675
Hi.Experts:
if(n is a special symbol) n=pop from stack2;
Could someone told me what's mean of "special symbol"?
Thanks!!
0

LVL 11

Expert Comment

ID: 8213803
It can be any specific data that marks something.
In your case it marks "End of data" in stack1 and need to
go to stack2.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and infâ€¦
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
###### Suggested Courses
Course of the Month13 days, 6 hours left to enroll

#### 578 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.