二、(25分)阅读下面的阶乘函数的递归算法，写出递推公式，并展开通推公式，求解时间复杂度。 Int Fact (int n). if(n==1) return 1; Else return n*Fact(n-1):

递推公式：$f(n) = n \times f(n-1)$

展开通推公式：

$$
\begin{aligned}
f(n) &= n \times f(n-1) \\
&= n \times (n-1) \times f(n-2) \\
&= n \times (n-1) \times (n-2) \times f(n-3) \\
&\cdots \\
&= n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 \\
&= n!
\end{aligned}
$$

时间复杂度：$O(n)$。因为需要递归调用 $n$ 次，每次调用的时间复杂度为 $O(1)$，所以总的时间复杂度为 $O(n)$。

相关问题

完成以下任务： （1）使用伪码写出递归算法来求解n的阶乘； （2）列出该递归算法的递推关系式； （3）使用替换法和迭代两种方法分别计算地推表达式的渐进表达式。

（1）使用伪代码描述递归算法来求解n的阶乘：

function factorial(n):
    if n == 0 or n == 1:      // 基线条件
        return 1
    else:
        return n * factorial(n - 1)  // 递归调用

（2）该递归算法的递推关系式为：
\[ \text{factorial}(n) = n \times \text{factorial}(n - 1) \]
当 \( n = 0 \) 或 \( n = 1 \) 时，递归结束。

（3）替换法（也称主定理）来计算递归表达式的渐进表达式：
对于上述的阶乘函数，我们知道 \( T(n) = n \cdot T(n-1) \)，其中 \( T(n) \) 表示计算 \( n! \) 的时间复杂度。这是一个基本情况下的递归操作，其时间复杂度可以用 \( O(n) \) 来表示，因为每次递归都多了常数级别的工作量。因此，递归树的每个节点的计算次数都是 \( n \) 级别的，所以整体上是线性的 \( O(n) \)。

迭代法计算渐进表达式：
我们可以用循环来避免递归，直接迭代计算阶乘：

def factorial_iterative(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

# 迭代方法的时间复杂度也是 O(n)

无论是递归还是迭代，它们的时间复杂度都是 \( O(n) \)。