递归十诫之第一诫（预备式）

前言

众所周知，快速排序算法是用递归实现的。那个时候对递归的认识就两句话：1. 找到终止条件。2. 找出递推表达式。那时候感觉会了，但又没完全会。感觉会是因为能够通过这两句话回忆起相应的代码；但没完全会是因为还是很模糊，当我尝试去追踪整个过程的时候，很快就绕晕了，并且换个类型的题目又不会了。找了很多例子，比如求和、阶乘、斐波那契、汉诺塔等等…但是还是不清晰，感觉例子还不够过。

写作目的

1. 是记录自己学习递归的过程。
2. 是帮助那些像曾经的我一样，在学算法时被递归折磨的phper。

学习方式

1. 首先，我的学习方式是于建国大佬的《学习观》： 学习要明确输入输出，要用例子重塑大脑链接。
   所以这个系列的博客将会有非常多的例子。
2. 其次，学习的过程最好是由简入繁，由浅入深。
   所以这个系列的博客将会从最简单的例子出发，再逐步抽象。

写作目标

希望我在写完这个系列的博客之后能够对递归有一个更清楚的认识，同时也能帮助到你培养起递归的思维模式。

如有错误，还望大佬指正。
闲话少说，进入正题。

十诫之第一诫（预备式）：在表述任意函数时，总将empty?作为诸问题之首。

需要用到的知识点：

1. array_shift:将数组的第一个单元移出数组。详情

   例子：
   $l = ['a','b','c'];
   $car = array_shift($l);
   var_dump($car); // 输出：'a';
   var_dump($l);   //  输出：['b','c'];

一、lat函数

我们先来看第一个函数：lat($l);

lat函数的代码如下：

function lat($l){
    if(empty($l)){
        // 当$l为空时，返回true。
        return true;
    }
    // 获取$l的第一个单元
    $car = array_shift($l);
    if(!is_array($car)){
        // 如果第一个单元不是数组，则递归调用。
        return lat($l);
    }else{
        // 如果第一个单元是数组，则返回false.
        return false;
    }
}

返回true的情况：

以$l = [‘a’,’b’,’c’]为例，即lat([‘a’,’b’,’c’]);
我们来先来理清一下这个过程：
进入lat函数之后，遇到的第一个问题便是：
if(empty($l))
1.1 即$l是否为空?显然不为空，接着往下走。
$car = array_shift($l);
1.2 移除$l的第一个元素，并将其保存在$car变量中，即$car = ‘a’。此时$l变为[‘b’,’c’]。
往下走便遇到了第二个问题：
(!is_array($car))
1.3 即$car是否为数组？ $car = ‘a’，不是数组。接着就调用lat函数，只不过这次的参数是[‘b’,’c’]，而不是原来的[‘a’,’b’,’c’]，即lat([‘b’,’c’]);
重复上述过程：
2.1 首先问$l是否为空？ 不为空，接着往下走。
2.2 执行 $car = array_shift($l);
此时：$car = ‘b’; $l = [‘c’];
2.3 再问$car是否为数组？显然不是，接着调用lat函数，参数为[‘c’],即：lat([‘c’]);
再次重复上述步骤：
3.1 首先问首先问$l是否为空？ 不为空，接着往下走。
3.2 执行 $car = array_shift($l);
此时：$car = ‘c’; $l = [];
3.3 再问$car是否为数组？显然不是，接着调用lat函数，参数为[],即lat([]);
再次重复上述步骤：
4.1 首先问首先问$l是否为空？ 这次为空，所以返回true。
结束了吗？ 还没有！还需要层层返回结果。
lat([])返回的结果为true，而lat([‘c’])返回的是lat([])，lat([‘b’,’c’])返回的是lat([‘c’]),lat([‘a’,’b’,’c’])返回的是lat([‘b’,’c’])。故最终的返回结果为true。
用文字描述可能不太清楚（如果读者不太熟悉这个过程，最好拿起笔来理一理这个过程。），还是用一张表来表示会更清晰一点：

我们来描述一下这个lat函数:

lat函数逐一检查列表的每一个单元，看看这个单元是否为一个数组，直到检查完所有单元。如果检查完所有单元都没遇到数组，则返回true，如果遇上了则返回false。

返回false的情况：

以$l = [‘a’,[‘b’],’c’]为例，即lat([‘a’,[‘b’],’c’]);
用表来表示这个过程：

二、member函数

接下来，我们来看一下第二个函数member($lat);

member函数代码如下：

function member($a,$lat)
{
    if (empty($lat)) {
        // lat为空就返回false。
        return false;
    } else {
        // 如果lat的第一个单元等于$a或者剩余lat（除去第一个单元的lat）中含有$a就返回true。
        return array_shift($lat) == $a||member($a, $lat);
    }
}

过程和上个函数类似就不再赘述了，还是用表来表示这个过程吧。

1. 先以$a=’b’,$lat=[‘a’,’b’,’c’]为例（返回true的例子）：

说明1： 运算符短路：$b = (true || foo());当第一个表达式为true时，foo()就没机会调用。详情请看这里。
因为’b’ == $a，为true，故不会再调用member(‘b’,[‘c’])函数。

2. 再以$a=’cd’,$lat=[‘a’,’b’,’c’]为例（返回false的例子）：

共同点

现在我们来找找这两个函数的共同点：
lat函数的第一个问题是什么？
if(empty($l))
member函数的第一个问题是什么？
if(empty($lat))
正如前面提到的十诫之第一诫所言：这两个函数的第一个问题都是empty?（是否为空）。当然这只是预备式，后续还有起飞式和终极式，敬请期待。

疑惑？

可能有读者会纳闷？这两个函数用循环实现不是更简单吗？确实更简单也更快。但是我是通过这些简单的例子才慢慢地走进了递归的大门，而且多一种思路也未尝不好。

本作品采用《CC 协议》，转载必须注明作者和本文链接