[recursive] Ackerman function

Ackermann function is an example of non primitive recursive function ; It requires two natural numbers as input values , Output a natural number . Its output value grows very fast , Is only (4,3) The output of is too large to be calculated accurately .

1920 Late S , Mathematician David · Hilbert's students Gabriel Sudan And William · Ackerman , The basis of calculation was being studied .Sudan Invented a recursive but not primitive recursive Sudan function .1928 year , Ackerman independently came up with another recursive but non primitive recursive function . His initial idea was a function of three variables A(m,n,p), The use of Conway chain arrow notation is m→n→p. Ackermann proved that it is a recursive function . Hilbert is in On the Infinite Guess this function is not primitive recursion . Where's Ackerman On Hilbert’s Construction of the Real Numbers It proves that . later Rozsa Peter and Raphael Robinson A similar function is defined , But only two variables .

Definition ：

                 { n+1;                             m=0,n>0   
  A(m,n) = { A(m-1,1);                      n=0,m>0   
                 { A(m-1,A(m,n-1))           n>0,m>0 

Code implementation

First of all, you must write a recursive function , The recursive knowledge of this problem is not complicated , Just write according to the title

Recursive function

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));
	}
}

you 're right , It's that simple . 

The whole program

#include<bits/stdc++.h>
using namespace std;
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));
	}
}
main(){
	int m,n;
	cin>>m>>n;
	cout<<ack(m,n);
}