Java Question I am stuck on. Ackermann’s Function is a recursive mathematical al

Question

Java Question I am stuck on.

Ackermann’s Function is a recursive mathematical algorithm that can be used to test how well a system optimizes its performance of recursion. The two-argument Ackermann’s function, is defined as follows for nonnegative integers m and n: a. Given the arguments m and n, write a method that solves the Ackermann’s function by using Recursion

          b. Given the arguments m and n, write a method that solves the Ackermann’s function by using Recursion with memoization

          c. Analyze the time and space complexity of each method.

Explanation / Answer

a. #include<stdio.h>

#include<stdlib.h>

int ackermann(int x, int y);

int count=0,indent=0;

int main(int argc, char **argv)

{

int x,y;

if(argc!=3)

{

printf(" Usage : %s <number1> <number2> ,argv[0]");

exit(0);

}

x=atoi(argv[1]);

y=atoi(argv[2]);

printf(" Ackermann Function with inputs (%d,%d) is %d ",x,y,ackermann(x,y));

printf(" Function called %d times. ,count");

}

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

}

b. #include<stdio.h>

#define MAX 10

int ackermann(int x, int y);

int count = 0;

int indent = 0;

int memory[MAX][MAX];

int main(int argc, char **argv)

{

int x,y;

int i,j;

if(argc!=3)

{

printf(" Usage : %s <number1> <number2> ,argv[0]");

exit(0);

}

x=atoi(argv[1]);

y=atoi(argv[2]);

for(i=0;i<MAX;i++)

for(j=0;j=MAX;j++)

memory[i][j]=-1;

printf(" Ackermann Function with inputs (%d,%d) is %d ",x,y,cacheAckermann(x,y));

printf(" Function called %d times. ",count");

}

int cacheAckermann(int x, int y)

{

int i;

if(x<0 || y<0 || x>=MAX || y>=MAX)

return -1;

if(memory[x][y]==-1)

{

printf(" ");

for(i=0;i<indent;i++)

printf("-");

indent++;

memory[x][y]=ackermann(x,y);

indent--;

printf(" ");

for(i=0;i<indent;i++)

printf("-");

printf("Return (%d,%d) : %d",x,y,memory[x][y]);

}

else

{

print(" ");

for(i=0;i<indent;i++)

printf("-");

printf("(%d,%d) - Cached",x,y);

printf(" ");

for(i=0;i<indent;i++)

printf("-");

printf("Return (%d,%d) : %d",x,y,memory[x][y]);

}

return memory[x][y];

}

int ackermann(int x, int y)

{

cout++;

printf("{%d,%d",x,y);

if (x<0 || y<0)

return -1;

if(x==0)

return y+1;

if(y==0)

return cacheAckermann(x-1,1);

return cacheAckermann(x-1,cacheAckermann(x,y-1));

}

c. If we talk about the time and space complexity of Ackermann's Function by recursion it takes less time but takes more space and if we talk about the time and space complexity of Ackermann's Function by using Recursion with memoization takes too much time but takes less space.

So hope you'll like the anwser if Yes then please give a Thumbs Up.Stay connected with Chegg for more help and answers Thankyou :)

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.