递归函数

递归就是函数调用自己。听起来有点绕，但有些问题用递归来解决特别自然，比如计算阶乘、遍历目录树等。

递归的基本概念

递归函数必须有两个要素：

1. 终止条件：什么时候停止递归
2. 递归调用：函数调用自身，参数要朝着终止条件变化

缺少终止条件会导致无限递归，最终栈溢出。

计算阶乘

阶乘是递归的经典例子：n! = n × (n-1) × ... × 1

factorial() {
    local n=$1
    
    # 终止条件
    if [ $n -le 1 ]; then
        echo 1
        return
    fi
    
    # 递归调用
    local prev=$(factorial $((n - 1)))
    echo $((n * prev))
}

result=$(factorial 5)
echo "5! = $result"

运行结果：

5! = 120

执行过程是这样的：

• factorial(5) 调用 factorial(4)
• factorial(4) 调用 factorial(3)
• factorial(3) 调用 factorial(2)
• factorial(2) 调用 factorial(1)
• factorial(1) 返回 1
• 逐层返回并计算

斐波那契数列

斐波那契数列：1, 1, 2, 3, 5, 8, 13... 每个数是前两个数之和：

fibonacci() {
    local n=$1
    
    if [ $n -le 2 ]; then
        echo 1
        return
    fi
    
    local a=$(fibonacci $((n - 1)))
    local b=$(fibonacci $((n - 2)))
    echo $((a + b))
}

for i in {1..10}; do
    result=$(fibonacci $i)
    echo -n "$result "
done
echo

运行结果：

1 1 2 3 5 8 13 21 34 55 

不过这个实现效率很低，因为会重复计算。fibonacci(10) 会调用 fibonacci(9) 和 fibonacci(8)，而 fibonacci(9) 又会调用 fibonacci(8)，重复了。实际使用时要注意性能问题。

遍历目录树

递归遍历目录是更实用的例子：

list_files() {
    local dir=$1
    local indent=${2:-""}
    
    for item in "$dir"/*; do
        if [ -d "$item" ]; then
            echo "${indent}📁 $(basename "$item")/"
            list_files "$item" "$indent  "
        elif [ -f "$item" ]; then
            echo "${indent}📄 $(basename "$item")"
        fi
    done
}

list_files "/tmp/test"

运行结果示例：

📁 dir1/
  📄 file1.txt
  📁 subdir/
    📄 file2.txt
📁 dir2/
  📄 file3.txt

计算目录大小

dir_size() {
    local dir=$1
    local total=0
    
    for item in "$dir"/*; do
        if [ -f "$item" ]; then
            local size=$(stat -c%s "$item" 2>/dev/null || stat -f%z "$item" 2>/dev/null)
            total=$((total + size))
        elif [ -d "$item" ]; then
            local sub_size=$(dir_size "$item")
            total=$((total + sub_size))
        fi
    done
    
    echo $total
}

size=$(dir_size "/tmp/test")
echo "目录大小：$((size / 1024)) KB"

递归深度限制

Shell 有递归深度限制，超过限制会报错：

deep_recurse() {
    local n=$1
    echo "深度：$n"
    deep_recurse $((n + 1))
}

deep_recurse 1

运行一段时间后会报错：

深度：1
深度：2
...
深度：500
bash: deep_recurse: recursion depth exceeded (recursion depth = 500)

默认限制通常是 500 层左右，可以通过环境变量调整，但不建议设太大。

尾递归优化

有些语言支持尾递归优化，可以把递归转换成循环。Shell 不支持，但我们可以手动转换。

递归版本：

sum_recursive() {
    local n=$1
    if [ $n -le 0 ]; then
        echo 0
        return
    fi
    local prev=$(sum_recursive $((n - 1)))
    echo $((n + prev))
}

循环版本（更高效）：

sum_loop() {
    local n=$1
    local total=0
    local i
    for ((i = 1; i <= n; i++)); do
        total=$((total + i))
    done
    echo $total
}

能用循环解决的问题，优先用循环，性能更好，也不会有栈溢出的风险。

小结

• 递归函数必须有终止条件，否则会无限循环
• 阶乘、斐波那契是经典的递归例子
• 遍历目录树是递归的实用场景
• Shell 有递归深度限制，约 500 层
• 能用循环解决的问题优先用循环