Как найти рекуррентное отношение из заданной рекурсивной функции

Question

Я прохожу старый набор экзаменов для курса по структурам данных и алгоритму и, похоже, не могу понять, как решить эту проблему.

Вопрос (d) Найти рекуррентное соотношение для числа умножений, выполненных с помощью следующего рекурсивного метода:

static int f(int N)
   {
       if (N > 1) return 2*f(N - 1);
       else return 3;
   }

Ответ: T(N) = T(N − 1) + 1

Я не до конца понимаю, как это соотношение находит число умножений?

T(2) = T(2 - 1) + 1 = 2

T(3) = T(3 - 1) + 1 = 3

Я попытался вставить 2 и 3 в отношение, но я до сих пор не вижу, как это количество умножений. Я на правильном пути?

Answer 1

Для f(N) у вас есть еще один рекурсивный вызов, чем для f(N-1), так что еще одно умножение, таким образом

T(N) = T(N-1) + 1

с базовым корпусом T(1) = 0.