递归算法详解

什么是递归算法？

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。一个方法或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归和迭代的区别

递归和迭代都是循环中的一种。

简单地说，递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环，而迭代与普通循环的区别是：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。

递归循环中，遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。当然很多情况都是多种循环混合采用，这要根据具体需求。

缺点

递归是不断调用自身的过程，由于每执行一次函数，都会开辟一块新的内存空间，问题规模较大时会占用大量内存，而且递归不断调用自身时，会导致系统的性能下降，对服务器的要求较高，其实就是一种以空间换时间的方法。

应用场景

什么样的问题才可以使用递归的方式求解呢？构成递归需要具备两个条件：
（1）子问题与原始问题为同样的事情，二者的求解方法是相同的，且子问题比原始问题更易求解。
（2）递归不能无限制地调用本身，必须有个递归出口。递归出口对应的情形相对简单，可以化简为非递归状况处理。

实例

发波那契数列
阶乘
树的遍历
遍历文件夹
汉诺塔
逆序打印字符串
求二叉树的深度

PHP 实现递归的三种方式

一、利用引用做参数

关于 PHP 引用的知识可以查看 PHP 官方文档
https://www.php.net/manual/zh/language.references.whatare.php

引用是指两个不同名的变量指向同一块存储地址，所以任何对存储地址的修改都会影响两个变量的值。

递归函数将引用作为参数，使其成为一个桥梁，形成两个函数间的数据共享。虽然两个函数看起来操作的是不同地址，但是实际上操作的是同一块内存地址。

<?php
function test( $a = 0, &$result = array() ) {
    $a++;
    if ( $a < 10 ) {
        $result[] = $a;
        test( $a, $result );
    }
    echo $a . "<br>";
    return $result;
}

echo "<pre>";
print_r( test() );
echo "</pre>";

输出结果：

10
9
8
7
6
5
4
3
2
1
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 8
    [8] => 9
)

二、利用全局变量

global 在函数内申明变量后，就变成外部变量的同名引用。变量的作用范围仍然在本函数范围内。改变这些变量的值，外部同名变量的值自然也改变了。
例如下面的代码，只需要在函数内部使用 global 引用外部的 $a，则函数内修改 $a 的值，外部的 $a 数值也会同步修改。

<?php
$a = 1;
function test(){
    global $a;
    $a++;
    echo $a;
}
test();
echo $a;

输出：

2
2

使用全局变量实现递归函数，代码如下：

<?php
function test($a=0,$result=array()){
  global $result;
  $a++;
  if ($a<10) {
    $result[]=$a;
    test($a,$result);
  }
  return $result;
}

三、利用静态变量

static的特点：仅在第一次调用函数的时候对变量进行初始化，并且保留变量值。

<?php
function test() {
    static $count = 0;
    echo $count;
    $count++;
}
test();
test();
test();
test();
test();

这一段代码的执行结果是多少？
是00000么？
必然不是。
是01234。
首先第一次调用 test(), static 对 $count 进行初始化，其后每一次执行完都会保留 $count 的值,不再进行初始化，相当于直接忽略了 static $count=0; 这一句。

因而将 static 应用到递归函数作用可想而知。在将需要作为递归函数间“桥梁”的变量利用static进行初始化，每一次递归都会保留”桥梁变量”的值。

<?php
function test($a=0){
  static $result=array();
  $a++;
  if ($a<10) {
    $result[]=$a;
    test($a);
  }
  return $result;
}

php 实现递归与无限分类的方法，代码如下

<?php
echo '<pre>';
$area = array(
    array( 'id'=>1, 'area'=>'北京', 'pid'=>0 ),
    array( 'id'=>2, 'area'=>'广西', 'pid'=>0 ),
    array( 'id'=>3, 'area'=>'广东', 'pid'=>0 ),
    array( 'id'=>4, 'area'=>'福建', 'pid'=>0 ),
    array( 'id'=>11, 'area'=>'朝阳区', 'pid'=>1 ),
    array( 'id'=>12, 'area'=>'海淀区', 'pid'=>1 ),
    array( 'id'=>21, 'area'=>'南宁市', 'pid'=>2 ),
    array( 'id'=>45, 'area'=>'福州市', 'pid'=>4 ),
    array( 'id'=>113, 'area'=>'亚运村', 'pid'=>11 ),
    array( 'id'=>115, 'area'=>'奥运村', 'pid'=>11 ),
    array( 'id'=>234, 'area'=>'武鸣县', 'pid'=>21 )
);

function t( $arr, $pid = 0, $lev = 0 ) {
    static $list = array();
    foreach ( $arr as $v ) {
        if ( $v['pid'] == $pid ) {
            echo str_repeat( ' ', $lev ).$v['area'].'<br />';
            //这里输出，是为了看效果
            $list[] = $v;
            t( $arr, $v['id'], $lev+1 );
        }
    }
    return $list;
}

$list = t( $area );
echo '<hr >';
print_r( $list );

输出：