面试题：Bash函数递归与迭代实现阶乘

Question

请分别使用Bash中的函数递归和迭代算法实现计算阶乘的功能，并解释两种方法在性能和资源使用上的差异。

Answer 1

1. 函数递归实现阶乘

factorial_recursive() {
    if [ $1 -eq 0 ] || [ $1 -eq 1 ]; then
        echo 1
    else
        local result=$(( $1 * $(factorial_recursive $(( $1 - 1 )) ) ))
        echo $result
    fi
}

调用示例：

factorial_recursive 5

2. 迭代算法实现阶乘

factorial_iterative() {
    local n=$1
    local result=1
    for (( i=1; i<=n; i++ )); do
        result=$(( result * i ))
    done
    echo $result
}

调用示例：

factorial_iterative 5

3. 性能和资源使用差异

• 性能：
  • 递归：递归实现的阶乘在每次调用函数时都需要进行压栈操作，保存当前函数的上下文信息，包括参数、局部变量等。当递归深度较大时，函数调用的开销会逐渐增大，导致性能下降。例如，计算100的阶乘，递归可能会因为频繁的函数调用而变慢。
  • 迭代：迭代通过循环的方式实现，每次循环只是简单的变量更新，没有函数调用的开销，因此在性能上通常优于递归。同样计算100的阶乘，迭代方式会更快。
• 资源使用：
  • 递归：由于递归调用需要不断压栈，会占用大量的栈空间。如果递归深度过大，可能会导致栈溢出错误。例如在一些系统中，栈空间有限，计算较大数的阶乘时递归容易出现栈溢出。
  • 迭代：迭代使用循环，不需要额外的栈空间来保存函数调用的上下文，只需要有限的几个变量来保存中间结果，因此在资源使用上更为节省，尤其是在处理较大规模数据时，优势明显。