Question

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.

Answer 1

22.

Step-by-step 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.