递归关系

Question

为什么递归阶乘算法的递推关系是这样的？

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……第二个递推关系成立（阶乘计算正确）而不是第一个。

Answer 1

我们通常使用递归关系来求算法的时间复杂度。

---

这里，函数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
不是你后面提到的。

---

就像河内塔的重现一样
当n＞0时，T(n)＝2T(n-1)+1；

更新：
一般来说，它与实施没有任何关系。
但是递归可以给出编程范式的直觉，例如如果 T(n)=2*T(n/2)+n （合并排序），这给出了分而治之的直觉，因为我们将 n 分成两半。

另外，如果你要解方程，它会给你运行时间带来限制。例如大哦符号。

Answer 2

看起来 T(n) 是递归阶乘算法的时间复杂度的递推关系，假设常数时间乘法。也许你误读了你的来源？

Answer 3

他说的不是阶乘递归，而是它的时间复杂度。
假设这是这种递归的伪代码：

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)

• 我假设不涉及尾递归消除。

第 2 行和第 3 行花费恒定时间 c1 和 c2。
4 号线也花费固定时间。然而，它调用阶乘(n-1)，这将需要一些时间T(n-1)。此外，一旦使用 T(n-1)，则可以忽略将 Factorial(n-1) 乘以 n 所需的时间。
整个函数的时间只是总和：T(n) = c1 + c2 + T(n-1)。
用大 O 表示法，可以将其简化为 T(n) = 1 + T(n-1)。

正如 Diam 指出的那样，这是一个平面递归，因此它的运行时间应该是 O(n)。但它的空间复杂度将是巨大的。

Answer 4

我假设你有错误的信息。正如您所观察到的，您引用的第二个递归关系是正确的。第一个仅生成自然数。

Answer 5

这个问题很令人困惑......你的第一个公式不是阶乘。对于所有 n，它只是 T(n) = n + 1。 n 的阶乘是前 n 个正整数的乘积：阶乘 (1) = 1。阶乘 (n) = n * 阶乘 (n-1)。你的第二个公式基本上是正确的。

Answer 6

T(n) = T(n-1) + 1 是 n 阶乘的正确递推方程。
该方程为您提供了计算 n 阶乘而不是 n 阶乘值的时间。

Answer 7

你在哪里找到第一个？这是完全错误的。

无论值是多少，每次都会加 1。

Answer 8

首先，您必须找到一个基本运算，在本例中它是乘法。每次递归都会发生一次乘法。所以
T(n) = T(n-1) +1
这个+1是基本运算（本例中是乘法）
T(n-1) 是下一个递归调用。

Answer 9

TL;DR：您问题的答案实际上取决于您定义的递归关系的顺序。也就是说，您问题中的序列 T_n 代表的是阶乘函数还是计算阶乘函数的运行时间成本^X。

---

阶乘函数

n、f_n 阶乘的递归定义为：

f< sub>n = n • f_n-1 对于 n > 0，f₀ = 1。

正如您所看到的，上面的方程实际上是一个递归关系，因为它是一个方程，与初始项一起使用（即， f₀ = 1），递归地定义一个序列（即阶乘函数，f<子>n）。

---

对计算阶乘的运行时间成本进行建模

现在，我们将找到一个模型来表示计算n 阶乘的运行时间成本。我们将T_n称为计算f_n的运行时间成本。

查看上面阶乘函数 f_n 的定义，其运行时间成本 T_n 将包括计算的运行时成本f_n-1（即，此成本为T_n-1）加上执行 n 和 f_n-1 之间的乘法的运行时间成本。乘法是在恒定时间内实现的。因此我们可以说T_n = T_n-1 + 1。

但是，T₀ 的值是多少？ T₀ 表示计算 f₀ 的运行时成本。由于 f₀ 的值最初根据定义已知，因此计算 f₀ 的运行时成本为实际上是恒定的。因此，我们可以说 T₀ = 1。

最后，我们得到的是：

T_n = T_n-1 + 1 for n > 0，T₀ = 1。

上面的这个方程也是一个递归关系。然而，它定义的（与初始项一起）是一个对计算阶乘函数的运行时间成本进行建模的序列。

---

^X_{考虑到递归关系中的序列如何被调用（即Tn），我认为它很可能代表后者，即计算阶乘函数的运行时间成本。}