algorithm - 如何从给定的递归函数中找到递归关系

Question

我正在复习我的数据结构和算法类(class)的旧考试集，但似乎无法弄清楚如何解决这个问题。

问题 (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。