Given the following recursive function:
// Pre-condition: y is non-negative.
int mysterious(int x, int y) {
if (y == 0) return x;
return 2*mysterious(x, y-1);
}
What is the return value of mysterious(3, 2)?
Here is my call stack:
return 2*mysterious(3, 2-1) => 2*3 => 6, 2*1 => mysterious(6,2)
return 2*mysterious(6, 2-1) => 6*2 => 12, 2*2 => mysterious(12, 2)
But it seems like y will never reach 0. What am I doing wrong?
mysterious(3, 2) = 2 * mysterious(3, 1) = 2 * 2 * mysterious(3, 0) = 2 * 2 * 3 = 12
if you expand that call you effectively have
(2*(2*(3))) == 12
Y only ever decreases (by 1 each call) so the function is clearly recursive and should terminate for y>=0
Each time mysterious is called (once by you, twice by recursion), y is decremented by 1.
So, you get (in mysterious)
3 2
3 1
3 0
the final value is 12 (3*2*2)
mysterious(3, 2)
y(==2) is not 0 therefore it
returns 2 * mysterious(3, 1)
mysterious(3,1)
y(==1) is not 0 so it
returns 2 * mysterious(3 , 0)
mysterious(3 , 0)
return 3 because y == 0
2 * 3 = 6
2 * 6 = 12
x is never modified, but with each recursive call y is reduced by one and when reaches the ground clause (if y == 0) it returns x (which from the first call is 3)
It's nothing else than
x * 2**y
or
mysterious(x, y) == x*pow(2, y)
so it could be very well defined for any value of y
