递归函数 #

一、递归基础 #

1.1 什么是递归 #

递归是函数调用自身的编程技术。递归函数必须包含：

基准条件（终止条件）
递归调用

bash

#!/bin/bash

# 简单递归示例
countdown() {
    local n=$1
    
    # 基准条件
    if (( n <= 0 )); then
        echo "发射!"
        return
    fi
    
    echo "倒计时: $n"
    # 递归调用
    countdown $((n - 1))
}

countdown 5

1.2 递归执行过程 #

bash

#!/bin/bash

# 带调试信息的递归
factorial() {
    local n=$1
    local depth=${2:-0}
    local indent=$(printf '%*s' $((depth * 2)) '')
    
    echo "${indent}factorial($n) 开始"
    
    # 基准条件
    if (( n <= 1 )); then
        echo "${indent}factorial($n) 返回 1"
        echo 1
        return
    fi
    
    # 递归调用
    local sub_result=$(factorial $((n - 1)) $((depth + 1)))
    local result=$((n * sub_result))
    
    echo "${indent}factorial($n) 返回 $result"
    echo $result
}

result=$(factorial 4)
echo "最终结果: $result"

二、经典递归示例 #

2.1 阶乘 #

bash

#!/bin/bash

factorial() {
    local n=$1
    
    # 基准条件
    if (( n <= 1 )); then
        echo 1
        return
    fi
    
    # 递归计算
    local prev=$(factorial $((n - 1)))
    echo $((n * prev))
}

# 计算5的阶乘
result=$(factorial 5)
echo "5! = $result"  # 输出: 120

2.2 斐波那契数列 #

bash

#!/bin/bash

fibonacci() {
    local n=$1
    
    # 基准条件
    if (( n <= 0 )); then
        echo 0
        return
    fi
    
    if (( n == 1 )); then
        echo 1
        return
    fi
    
    # 递归计算
    local a=$(fibonacci $((n - 1)))
    local b=$(fibonacci $((n - 2)))
    echo $((a + b))
}

# 计算前10个斐波那契数
echo "斐波那契数列:"
for i in {0..10}; do
    echo -n "$(fibonacci $i) "
done
echo ""

2.3 求和 #

bash

#!/bin/bash

# 递归求和
sum() {
    local n=$1
    
    if (( n <= 0 )); then
        echo 0
        return
    fi
    
    local prev=$(sum $((n - 1)))
    echo $((n + prev))
}

result=$(sum 100)
echo "1到100的和: $result"

# 数组求和
array_sum() {
    local arr=("$@")
    local len=${#arr[@]}
    
    if (( len == 0 )); then
        echo 0
        return
    fi
    
    if (( len == 1 )); then
        echo "${arr[0]}"
        return
    fi
    
    local first=${arr[0]}
    local rest=("${arr[@]:1}")
    local sub_sum=$(array_sum "${rest[@]}")
    
    echo $((first + sub_sum))
}

numbers=(1 2 3 4 5)
result=$(array_sum "${numbers[@]}")
echo "数组求和: $result"

2.4 最大公约数 #

bash

#!/bin/bash

gcd() {
    local a=$1
    local b=$2
    
    # 基准条件
    if (( b == 0 )); then
        echo $a
        return
    fi
    
    # 递归调用（欧几里得算法）
    gcd $b $((a % b))
}

result=$(gcd 48 18)
echo "GCD(48, 18) = $result"

三、递归遍历 #

3.1 目录遍历 #

bash

#!/bin/bash

traverse_dir() {
    local dir="$1"
    local indent="${2:-}"
    
    # 检查目录
    if [[ ! -d "$dir" ]]; then
        return
    fi
    
    # 遍历目录内容
    for item in "$dir"/*; do
        local name=$(basename "$item")
        
        if [[ -d "$item" ]]; then
            echo "${indent}📁 $name/"
            traverse_dir "$item" "$indent  "
        elif [[ -f "$item" ]]; then
            echo "${indent}📄 $name"
        fi
    done
}

traverse_dir "/path/to/directory"

3.2 文件查找 #

bash

#!/bin/bash

find_files() {
    local dir="$1"
    local pattern="$2"
    
    # 检查目录
    if [[ ! -d "$dir" ]]; then
        return
    fi
    
    # 遍历目录
    for item in "$dir"/*; do
        if [[ -d "$item" ]]; then
            # 递归搜索子目录
            find_files "$item" "$pattern"
        elif [[ -f "$item" ]]; then
            # 检查文件名匹配
            local name=$(basename "$item")
            if [[ "$name" == *"$pattern"* ]]; then
                echo "$item"
            fi
        fi
    done
}

find_files "/home/user" "config"

3.3 JSON解析 #

bash

#!/bin/bash

parse_json_level() {
    local json="$1"
    local level="${2:-0}"
    local indent=$(printf '%*s' $((level * 2)) '')
    
    # 简单的JSON解析示例
    # 实际应用中应使用jq等工具
    
    if [[ "$json" =~ ^\{ ]]; then
        echo "${indent}对象:"
        # 递归解析对象内容
        # ...
    elif [[ "$json" =~ ^\[ ]]; then
        echo "${indent}数组:"
        # 递归解析数组内容
        # ...
    else
        echo "${indent}值: $json"
    fi
}

四、递归优化 #

4.1 尾递归优化 #

bash

#!/bin/bash

# 普通递归（非尾递归）
factorial() {
    local n=$1
    
    if (( n <= 1 )); then
        echo 1
        return
    fi
    
    local prev=$(factorial $((n - 1)))
    echo $((n * prev))  # 递归后还有计算
}

# 尾递归形式
factorial_tail() {
    local n=$1
    local acc="${2:-1}"
    
    if (( n <= 1 )); then
        echo $acc
        return
    fi
    
    # 尾递归调用（最后一步是递归）
    factorial_tail $((n - 1)) $((n * acc))
}

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

4.2 记忆化 #

bash

#!/bin/bash

# 使用全局数组缓存结果
declare -A fib_cache

fibonacci_memo() {
    local n=$1
    
    # 检查缓存
    if [[ -n "${fib_cache[$n]}" ]]; then
        echo "${fib_cache[$n]}"
        return
    fi
    
    # 基准条件
    if (( n <= 0 )); then
        fib_cache[0]=0
        echo 0
        return
    fi
    
    if (( n == 1 )); then
        fib_cache[1]=1
        echo 1
        return
    fi
    
    # 递归计算并缓存
    local a=$(fibonacci_memo $((n - 1)))
    local b=$(fibonacci_memo $((n - 2)))
    local result=$((a + b))
    
    fib_cache[$n]=$result
    echo $result
}

# 计算大数
result=$(fibonacci_memo 40)
echo "F(40) = $result"

4.3 迭代替代 #

bash

#!/bin/bash

# 递归版本
factorial_recursive() {
    local n=$1
    
    if (( n <= 1 )); then
        echo 1
        return
    fi
    
    local prev=$(factorial_recursive $((n - 1)))
    echo $((n * prev))
}

# 迭代版本（更高效）
factorial_iterative() {
    local n=$1
    local result=1
    
    for (( i=2; i<=n; i++ )); do
        ((result *= i))
    done
    
    echo $result
}

# 性能对比
time factorial_recursive 20
time factorial_iterative 20

五、递归实战 #

5.1 汉诺塔 #

bash

#!/bin/bash

hanoi() {
    local n=$1
    local from=$2
    local to=$3
    local aux=$4
    
    if (( n == 1 )); then
        echo "移动盘子 1 从 $from 到 $to"
        return
    fi
    
    hanoi $((n - 1)) "$from" "$aux" "$to"
    echo "移动盘子 $n 从 $from 到 $to"
    hanoi $((n - 1)) "$aux" "$to" "$from"
}

echo "汉诺塔问题（3个盘子）:"
hanoi 3 "A" "C" "B"

5.2 二分查找 #

bash

#!/bin/bash

binary_search() {
    local -n arr=$1
    local target=$2
    local left=${3:-0}
    local right=${4:-$((${#arr[@]} - 1))}
    
    # 基准条件
    if (( left > right )); then
        echo -1  # 未找到
        return
    fi
    
    local mid=$(( (left + right) / 2 ))
    
    if (( arr[mid] == target )); then
        echo $mid
        return
    fi
    
    if (( arr[mid] > target )); then
        binary_search arr $target $left $((mid - 1))
    else
        binary_search arr $target $((mid + 1)) $right
    fi
}

# 测试
sorted_numbers=(1 3 5 7 9 11 13 15 17 19)
index=$(binary_search sorted_numbers 7)
echo "数字7的索引: $index"

5.3 快速排序 #

bash

#!/bin/bash

quicksort() {
    local -n arr=$1
    local left=${2:-0}
    local right=${3:-$((${#arr[@]} - 1))}
    
    if (( left >= right )); then
        return
    fi
    
    # 分区
    local pivot=${arr[$right]}
    local i=$((left - 1))
    
    for (( j=left; j<right; j++ )); do
        if (( arr[j] <= pivot )); then
            ((i++))
            # 交换
            local temp=${arr[$i]}
            arr[$i]=${arr[$j]}
            arr[$j]=$temp
        fi
    done
    
    # 放置pivot
    ((i++))
    local temp=${arr[$i]}
    arr[$i]=${arr[$right]}
    arr[$right]=$temp
    
    local pivot_index=$i
    
    # 递归排序
    quicksort arr $left $((pivot_index - 1))
    quicksort arr $((pivot_index + 1)) $right
}

# 测试
numbers=(5 2 8 1 9 3 7 4 6)
echo "排序前: ${numbers[@]}"
quicksort numbers
echo "排序后: ${numbers[@]}"

5.4 树遍历 #

bash

#!/bin/bash

# 使用关联数组表示树
declare -A tree_left
declare -A tree_right
declare -A tree_value

# 构建树
build_tree() {
    tree_value[1]="A"
    tree_left[1]=2
    tree_right[1]=3
    
    tree_value[2]="B"
    tree_left[2]=4
    tree_right[2]=5
    
    tree_value[3]="C"
    tree_left[3]=6
    tree_right[3]=7
    
    tree_value[4]="D"
    tree_value[5]="E"
    tree_value[6]="F"
    tree_value[7]="G"
}

# 前序遍历
preorder() {
    local node=$1
    
    if [[ -z "$node" || "$node" == "0" ]]; then
        return
    fi
    
    echo -n "${tree_value[$node]} "
    preorder "${tree_left[$node]}"
    preorder "${tree_right[$node]}"
}

# 中序遍历
inorder() {
    local node=$1
    
    if [[ -z "$node" || "$node" == "0" ]]; then
        return
    fi
    
    inorder "${tree_left[$node]}"
    echo -n "${tree_value[$node]} "
    inorder "${tree_right[$node]}"
}

# 后序遍历
postorder() {
    local node=$1
    
    if [[ -z "$node" || "$node" == "0" ]]; then
        return
    fi
    
    postorder "${tree_left[$node]}"
    postorder "${tree_right[$node]}"
    echo -n "${tree_value[$node]} "
}

# 测试
build_tree

echo "前序遍历:"
preorder 1
echo ""

echo "中序遍历:"
inorder 1
echo ""

echo "后序遍历:"
postorder 1
echo ""

六、递归注意事项 #

6.1 栈溢出 #

bash

#!/bin/bash

# 可能导致栈溢出
infinite_recursion() {
    infinite_recursion  # 无限递归
}

# 设置最大递归深度
MAX_DEPTH=100

safe_recursion() {
    local depth=${1:-0}
    
    if (( depth >= MAX_DEPTH )); then
        echo "达到最大递归深度"
        return 1
    fi
    
    safe_recursion $((depth + 1))
}

6.2 性能考虑 #

bash

#!/bin/bash

# 递归版本（较慢）
fib_recursive() {
    local n=$1
    (( n <= 1 )) && { echo $n; return; }
    echo $(( $(fib_recursive $((n-1))) + $(fib_recursive $((n-2))) ))
}

# 迭代版本（更快）
fib_iterative() {
    local n=$1
    local a=0 b=1
    
    for (( i=0; i<n; i++ )); do
        local temp=$((a + b))
        a=$b
        b=$temp
    done
    
    echo $a
}

# 对于大数，使用迭代
result=$(fib_iterative 40)
echo "F(40) = $result"

七、总结 #

7.1 递归要点 #

要点	说明
基准条件	必须有终止条件
递归调用	问题规模必须缩小
局部变量	使用local避免变量冲突
性能	考虑使用记忆化或迭代

7.2 下一步 #

你已经完成了函数部分的学习，接下来让我们学习字符串基础，深入了解字符串处理！