阶乘的递归关系

Question

我正在通过在（幻灯片 7 和 8）找到的幻灯片研究复发：

http://www.cs.ucf.edu/courses/cop3502h/spring2012/Lectures/Lec8_RecurrenceRelations.pdf

我不能接受（可能我没看对）阶乘的递归方程是：

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

考虑函数的操作次数（“*”和“-”）时：

int factorial(int n) {
 if (n == 1)
 return 1;
 return n * factorial(n-1);
}

如果我们使用 n = 5，我们将通过上面的公式得到 6，而真正的 subs 和 molts 数量是 8。

我的老师也告诉我们，如果只分析“*”的个数，那就是：

T(n) = T(n-1)+1.

同样，如果我使用 n = 5，我会得到 5，但如果你在纸上这样做，你将得到 4 次乘法。

我也在论坛上查过，但是这个问题比地狱更混乱： Recurrence Relation

谁能帮我理解一下？谢谢。

Answer 1

if we use n = 5 we will get 6 by the formula above while the real number of subs and molts are 8.

看来幻灯片是在计算运算次数，而不仅仅是减法和乘法。特别是，return 语句被计为一个操作。 （幻灯片说，"if it’s the base case just one operation to return."）

因此，减法和乘法的实际次数是8次，但操作次数是9次。如果n是5，那么，展开递归，我们得到1 + 2 + 2 + 2 + 2 = 9次操作，这对我来说很合适。