Рекурсивная функция

Question

Учитывая следующую рекурсивную функцию:

// Pre-condition: y is non-negative.
int mysterious(int x, int y) {
    if (y == 0) return x;
    return 2*mysterious(x, y-1);
}

Что такое возвращаемое значение таинственного (3, 2)?

Вот мой стек вызовов:

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)

Но кажется, что у тебя никогда не будет 0. Что я делаю не так?

Answer 1

mysterious(3, 2)

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

Answer 2

Это не что иное, как

x * 2**y

или

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

, поэтому его можно очень хорошо определить для любого значения y

Answer 3

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 никогда не изменяется, но при каждом рекурсивном вызове y уменьшается на единицу, а когда достигает основного предложения (if y == 0), возвращается x (который при первом вызове равен 3)

Answer 4

Каждый раз, когда вызывается таинственное (один раз вами, дважды рекурсией), y уменьшается на 1.

Итак, вы получите (загадочно)

3 2
3 1
3 0

окончательное значение 12 (3 * 2 * 2)

Answer 5

если вы расширите этот вызов, у вас фактически будет

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

Y только когда-либо уменьшается (на 1 каждый вызов), поэтому функция явно рекурсивна и должна завершаться для y>=0