Recursive function

Question

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 the 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 looks like y will never reach 0. What am I doing wrong?

Answer 1

  mysterious (3, 2)

 = 2 * mysterious (3, 1)
 = 2 * 2 * mysterious (3, 0)
 = 2 * 2 * 3
 = 12

Answer 2

if you deploy this call you have

 (2*(2*(3))) == 12 

Y only decreases (by 1 each call), therefore the function is explicitly recursive and should end for y>=0

Answer 3

Each time a mysterious one is called (once to you, twice by recursion), y is reduced by 1.

So you get (in the mysterious)

3 2
3 1
thirty

final value is 12 (3 * 2 * 2)

Answer 4

 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 never changes, but with each recursive call, y decreases by one, and when it reaches the ground clause ( if y == 0 ), it returns x (which from the first call is 3)

Answer 5

It is nothing but

 x * 2**y 

or

 mysterious(x, y) == x*pow(2, y) 

therefore, it can be very well defined for any y value