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
6
Medium Priority
?
3,224 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
  • 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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

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

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.

Join & Ask a Question