Given a recursive function as below. Predict the output for the inputs given. Show the steps.

int X (int n)

{

if (n==1) return 5;

else

return n + X (n/2);

}

Predict the value of X (10), show the steps of finding that out.

22.

Explanation:

First call will be made to X (10). Since 10 is not equal to 1 else will be executed

X (10) = 10+X (5) ... (1)

X (5) will be called in the call stack again else will be executed and it will return

X (5) = 5+X (2) ... (2)

X (2) will be called and else will get executed and it will return.

X (2) = 2+X (1) ... (3)

Now the argument is 1 if will be executed. Hence X (1) will return 5.

The value of X (2) will be 7. So the value of X (5) will be 5+7=12.

X (10) = 10 + 12=22.