笔记大全

php中构成递归需具备的条件有哪些

更新时间：2023-10-05

php中构成递归需具备的条件

1. 递归终止条件

在编写递归代码时，必须定义一个递归终止条件。递归函数在执行时，会不断地调用自身，直到达到终止条件，才会结束递归。

    function recursion($num) {
      if ($num <=0) {
        return 0; // 终止条件
      } else {
        return $num + recursion($num - 1); // 递归调用
      }
    }
    echo recursion(5); // 输出15

2. 问题的规模不断缩小

在编写递归代码时，必须保证问题的规模不断缩小。也就是说，每次递归调用时，问题的规模都比原来的规模要小。

    function fibonacci($num) {
      if ($num==0 || $num==1) {
        return $num; // 终止条件
      } else {
        return fibonacci($num - 1) + fibonacci($num - 2); // 递归调用
      }
    }
    echo fibonacci(6); // 输出8

3. 问题可分解为多个子问题

在编写递归代码时，必须将问题分解为多个子问题，每个子问题都可以通过相同的方式解决。然后通过递归调用解决这些子问题。

    function hanoi($n, $a, $b, $c) {
      if ($n==1) {
        echo "Move disk 1 from $a to $c 
"; // 终止条件
      } else {
        hanoi($n - 1, $a, $c, $b); // 将n-1个盘子从a移动到b
        echo "Move disk $n from $a to $c 
";
        hanoi($n - 1, $b, $a, $c); // 将n-1个盘子从b移动到c
      }
    }
    hanoi(3, 'A', 'B', 'C'); // 输出汉诺塔的移动步骤

4. 递归调用过程中的传参问题

在编写递归代码时，需要注意递归调用过程中的传参问题。每次递归调用都应该传递必要的参数，以保证递归函数正常执行。

    function binary_search($arr, $left, $right, $key) {
      if ($left > $right) {
        return -1; // 终止条件
      } else {
        $mid=intval(($left + $right) / 2);
        if ($arr[$mid]==$key) {
          return $mid;
        } else if ($arr[$mid] > $key) {
          return binary_search($arr, $left, $mid - 1, $key); // 递归调用
        } else {
          return binary_search($arr, $mid + 1, $right, $key); // 递归调用
        }
      }
    }
    $arr=array(1, 3, 4, 5, 7, 8, 10);
    $key=5;
    $index=binary_search($arr, 0, count($arr) - 1, $key);
    echo "Index of $key in \$arr is $index 
";

总之，php中构成递归需具备的条件包括递归终止条件、问题的规模不断缩小、问题可分解为多个子问题和递归调用过程中的传参问题。只有满足上述条件的递归函数才能正常执行，否则容易导致程序崩溃、死循环等问题。

c语言编程笔录