?
Solved

Nonrecursive algorithm of ackermann function

Posted on 2003-03-24
6
Medium Priority
?
3,079 Views
Last Modified: 2007-12-19
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
Comment
Question by:TKD
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
6 Comments
 

Expert Comment

by:Getch
ID: 8195831
**** down,and think...
0
 
LVL 11

Accepted Solution

by:
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...

Hope this will help you to proceed with your task.
0
 

Author Comment

by:TKD
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 11

Expert Comment

by:dimitry
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

by:TKD
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

by:dimitry
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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

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 how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
Suggested Courses
Course of the Month13 days, 15 hours left to enroll

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

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

Join & Ask a Question