Ackermann Function is the simplest example of a well defined total function which is compatible but not primitive recursive. It grows faster than an exponential function.
/* Ackermann Function */ #include<stdio.h> #include<stdlib.h> int count = 0, indent = 0; int ackermann(int x, int y) { count++; if(x<0 || y<0) return -1; if(x==0) return y+1; if(y==0) return ackermann(x-1,1); return ackermann(x-1,ackermann(x,y-1)); } int main() { int x,y; printf("Enter values for x and y : "); scanf("%d%d",&x,&y); printf("Result is %d\n",ackermann(x,y)); printf("\nFunction called %d times.\n",count); }