NOIP -- recursive to non recursive solution of Ackerman function

ackerman function (ackerman function, hereinafter referred to as ack function) is a two parameter recursive function. The recursive calculation code is as follows

int ack(int m,int n)
{    
   if (m==0)        
    return n+1;    
    else if (n==0)        
    return ack(m-1,1);    
    else     return ack(m-1,ack(m,n-1)); }

 

Like Dirichlet function, ack function has a place in the history of Mathematics (Computational Science) in order to clarify a certain concept.  
The ack function was originally proposed as an example of nonlinear chain recursion. It grows rapidly. In fact, when m > 3, the exponential growth of n is much higher than that of linear recursion (the growth of M is faster). However, it is counter intuitive. Even if the ack(4,1) is calculated accurately, it cannot be done. Even if the ack(3,3) is 61. If you do not remember the search, you need to recurse more than 2000 times to calculate it! If you do not consider the general term of the exponential growth of ack(3,n) and are confused by small numbers and try to calculate directly, you will have no clue. Therefore, ack function is widely used in computer preliminaries, written tests and independent entrance examinations of mathematics.  
Since the ack function grows so fast, the inverse function of ack(m,1) grows very slowly. In fact, the path compressed parallel query set has been queried for a long time, and the average complexity of each query is at the level of anti Ackerman function (that is, log * level. As for why, I wanted to know this problem at the latest in 2012, and now I finally know... I'm afraid I can't know it in a short time (~ ^ ~). There is a derivation of this in the introduction, and interested students can go and have a look). Well, this is some interesting cold knowledge, The origin of ack and my history.  
I thought my fate with ack didn't make any new progress after knowing how to do it in the preliminaries. At most, I talked about this problem later, but I never thought I would encounter this function in a strange way. The meaningful and famous function in the history of science, such as Dirichlet function, and ACK function is as white as new.

Recently, I learned the assembly principle in ics and the recursive method of numerical stack. In fact, the two are interlinked. Although I haven't written specific assembly code, I probably know how to implement function calls with stack and how to implement recursion with stack mechanism. I decided to find an example. I compiled a complex problem - the non recursive implementation of ackerman function (non recursion of recursive function).  
After some debugging, I'm right, but I'm still confused. It seems that I need to strengthen theoretical learning, but I have to say this is a good example.

int Ack(int M,int N)
{    
   int top=0,m,n;    
   int stack[10000][4]={{M,N}};//Record information m,n,Ack(m,n), jump exit type;    while (true)    {        m=stack[top][0];        n=stack[top][1];        
   if (m==0)            
   stack[top][2]=n+1;        
   else if (n==0)        {            top++;            
   stack[top][0]=m-1;            
   stack[top][1]=1;            
   stack[top][3]=1;            continue;            l1:            
   stack[top][2]=stack[top+1][2];        }        else        {            top++;            
   stack[top][0]=m-1;            top++;            
   stack[top][0]=m;            
   stack[top][1]=n-1;            
   stack[top][3]=2;            
   continue;            l2:            
   stack[top][1]=stack[top+1][2];            
   stack[top][3]=3;            
   continue;            l3:            
   stack[top][2]=stack[top+1][2];        }        
   if (top==0)            
   break;        top--;        
   switch (stack[top+1][3])        {            
   case 1:goto l1;            
   case 2:goto l2;            
   case 3:goto l3;        }    }    return stack[0][2]; }



NOIP informatics video address

Video address

Link: https://pan.baidu.com/s/1tHo1DFMaDuMZAemNH60dmw  
Extraction code: 7jgr

Posted by burzvingion on Mon, 09 May 2022 13:58:06 +0300