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

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。