8.6 递归函数（简单了解）

递归函数是指在函数内部调用自身的函数，常用于解决具有递归结构的问题。

基本原理

递归函数通常包含两个部分：

1. 基础情况：递归的终止条件
2. 递归步骤：调用自身解决子问题

示例代码

<?php
// 计算阶乘
function factorial($n) {
    // 基础情况
    if ($n <= 1) {
        return 1;
    }
    // 递归步骤
    return $n * factorial($n - 1);
}

echo "5的阶乘: " . factorial(5) . "<br>";
echo "10的阶乘: " . factorial(10) . "<br>";

// 计算斐波那契数列
function fibonacci($n) {
    // 基础情况
    if ($n <= 1) {
        return $n;
    }
    // 递归步骤
    return fibonacci($n - 1) + fibonacci($n - 2);
}

echo "<br>斐波那契数列前10项:<br>";
for ($i = 0; $i < 10; $i++) {
    echo fibonacci($i) . " ";
}
echo "<br>";

// 遍历目录（递归）
function listFiles($directory) {
    $files = scandir($directory);
    foreach ($files as $file) {
        if ($file != "." && $file != "..") {
            $path = $directory . "/" . $file;
            if (is_dir($path)) {
                echo "目录: $path<br>";
                listFiles($path); // 递归调用
            } else {
                echo "文件: $path<br>";
            }
        }
    }
}

// 注意：取消注释下面的代码会遍历当前目录
echo "<br>遍历当前目录:<br>";
// listFiles(".");

// 二分查找（递归）
function binarySearch($array, $target, $low, $high) {
    // 基础情况：未找到
    if ($low > $high) {
        return -1;
    }
    
    $mid = floor(($low + $high) / 2);
    
    // 基础情况：找到目标
    if ($array[$mid] == $target) {
        return $mid;
    }
    
    // 递归步骤
    if ($array[$mid] > $target) {
        return binarySearch($array, $target, $low, $mid - 1);
    } else {
        return binarySearch($array, $target, $mid + 1, $high);
    }
}

$numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
$target = 11;
$result = binarySearch($numbers, $target, 0, count($numbers) - 1);
echo "<br>在数组中查找 $target，位置: $result<br>";
?>

注意事项

1. 递归函数必须有明确的终止条件，否则会导致无限递归
2. 递归函数可能会导致栈溢出，对于深层递归需要注意
3. 递归函数的效率可能不如迭代方法，特别是对于大数据量
4. 递归函数的代码通常更简洁易懂，适合解决具有递归结构的问题

练习

1. 使用递归函数计算1到n的和
2. 使用递归函数实现辗转相除法求最大公约数
3. 使用递归函数反转字符串