JEST Sample Question-2

Question

Consider the following function, defined by a recursive program:
function AP(x,y: integer) returns integer;
{if
{x = 0 then return y+1}
else if { y = 0 then return AP(x-1,1)}
else
return AP(x-1, AP(x,y-1))

}

(a) Show that on all nonnegative arguments x and y, the function AP terminates.

(b) Show that for any x, AP(x, y) > y.

Answer 1

int AP(x,y){

        if(x==0)

              return y+1;

       elseif(y==0)

              return AP(x-1,1)

      else

             return AP(x-1, AP(x,y-1))

}

(a) Show that on all nonnegative arguments x and y, the function AP terminates.

 

Base case here is if(x==0) , when is this base case reachable ? only when x=0 , either provided as input or as a result of the recursion functional call.

Let's take cases here :-

1. Both  x and y are negative:-

the "else" statement would always hit and it would cause an infinite number of recursive calls since y will never be 0 , because y is always decrementing here.

And since this is an arbitrary programming language , nothing has been given regarding the stack space.Practically it should terminate on stack overlow , but the case can be rejected here .

2. x is positive , y is negative ,same case here , x=0 case will never be reached , since y will never be 0 to trigger the y==0 if condition .

Thus termination would occur only on stack overflow.

3. x is negative, y is positive .

surely y==0 if condition will be hit in some course of the recursive tree , but while doing x-1 , x=0 if clause will never be triggered , thus in this case too there will be a whole lot of recursive function calls.

4. x and y are both are positive .

At first , AP(x-1,AP(x,0)) would be reached , leading to a triggering of the elseif(y==0){return AP(x-1,1)} recursive call , 

Let's take an example here .

AP(1,1) -- > AP(0,AP(1,0)).

AP(1,0) - > AP(0,1) . here x=0 , would return 2 here.

And AP(0,2) will give 3 as final output .

Thus this case terminates.

So the function will terminate if and only if both x and y have a possibility to become 0 in the due course of the recursive calls.

(b) Show that for any x, AP(x, y) > y.

 

here also there can be three cases :-

1. x>y 

2. x = y

3. x<y

Let's take the first case here,

1. x>y 

AP(2,1) leads to AP(1,3)[Simple working , can be checked] . Here itself we can see that final value returned would be larger than y.

2. x=y

AP(1,1) returns 3 , which is greater than y.

3.x<y

AP(1,3) returns answer greater than 3 , precisely it's 5 .

AP(1,3) --- > AP(0,AP(1,2))

AP(1,2) --> AP(0,AP(1,1))

AP(1,1) --> AP(0,AP(1,0)) 

AP(1,0) --> AP(0,1)

AP(0,1) returns 2 to AP(1,0).

AP(0,2) returns 3 to AP(1,1)

AP(0,3) returns 4 to AP(1,2)

AP(0,4) returns 5 to AP(1,3).

Thus here final o/p is 5.