Question

Consider the iterative method below designed to sum a range of values from x to y.

public static int fun(int x, int y) {

int ans = 0;

for(int i = x; i <= y; i++)

ans = ans + i;

return ans;

}

Which of the following recursive methods are algorithmically equivalent to the iterative method shown above:

I.

public static int fun(int x, int y) {

if(x == y)

return 0;

else return x + (x + 1, y);

}

II.

public static int fun(int x, int y) {

if(x == y)

return 0;

else return y + (x, y - 1);

}

III.

public static int fun(int x, int y) {

if(x == y)

return 0;

else return y + (x + 1, y);

}

A. I only

B. I and II only

C. I and III only

D. II only

Answer 1

Itrative method

public static int fun(int x, int y)

{

int ans = 0;

for(int i = x; i <= y; i++)

ans = ans + i;

return ans;

}

assume x = 1 and y = 4

so here for loop iterate 1 to 4 then

ans = 1 + 2 + 3 + 4

ans = 10

Recursive method

1) public static int fun(int x, int y)

{

if(x == y)

return 0;

else return x + (x + 1, y);

}

same assume here x = 1 and y = 3

call fun(1 , 4)

1 + fun(2 , 4 )

2 + fun (3 , 4)

3 + fun(4 , 4)

fun (4 , 4) true return 0  

fun (4 , 4) = 0

fun(3 , 4) = 3 + 0

fun (2, 4) = 2 + 3 + 0

fun(1 , 4) = 1 + 2 + 3 + 0

return 6

it 's not equivalent to itaretive method

---------------------------------------------------------------------------------------------

2) public static int fun(int x, int y)

{

if(x == y)

return 0;

else return y + (x, y - 1);

}

same assume here x = 1 and y = 4

call fun(1 , 4)

4 + fun(1 , 3 )

3 + fun (1 , 2)

2 + fun(1 , 1)

fun (1 , 1) true return 0  

fun (1 , 1) = 0

fun(1 , 2) = 2 + 0

fun(1, 3) = 3 + 2 + 0

fun(1 , 4) = 4 + 3 + 2 + 0

return 9

it 's not equivalent to itaretive method

---------------------------------------------------------------------------------------------

3) public static int fun(int x, int y)

{

if(x == y)

return 0;

else return y + (x + 1, y);

}

same assume here x = 1 and y = 4

call fun(1 , 4)

4 + fun(2 , 4 )

4 + fun (3 , 4)

4 + fun(4 , 4)

fun (4 , 4) true return 0  

fun (4 , 4) = 0

fun(3 , 4) = 4 + 0

fun(2 , 4) = 4 + 4 + 0

fun(1 , 4) = 4 + 4 + 4 + 0

return 12

it 's not equivalent to itaretive method

---------------------------------------------------------------------------------------------

all three recursive method are not equivalent to the iterative method,