为什么递归阶乘算法的递推关系是这样的？
T(n)=1 for n=0
T(n)=1+T(n-1) for n>0
为什么不是这个呢？
T(n)=1 for n=0
T(n)=n*T(n-1) for n>0
输入 n 的值，即 1,2,3,4……第二个递推关系成立（阶乘计算正确）而不是第一个。
我们一般使用递推关系求算法的时间复杂度。
这里，函数 T(n) 实际上并不是用于计算阶乘的值，而是告诉您阶乘算法的时间复杂度。
这意味着求 n 的阶乘比 n-1 的阶乘多需要 1 次运算
（即 T(n)=T(n-1)+1）等等。
所以递归阶乘算法的正确递归关系是
T(n)=1（n=0）
T(n)=1+T(n-1) 对于 n>0
不是你后面提到的。
就像河内塔的重现一样
T(n)=2T(n-1)+1（n>0）；
更新：
一般来说，它与实施没有任何关系。
但是递归可以给出编程范式的直觉，例如如果 T(n)=2*T(n/2)+n （合并排序），这给出了分而治之的直觉，因为我们将 n 分成两半。
另外，如果你要解方程，它会给你运行时间带来限制。例如大哦符号。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
