递归十诫之第二诫

递归十诫之第二诫：使用array_merge函数来构建数组。

上篇博客——递归十诫之第一诫（预备式）说到：将empty作为诸问题之首。

本篇博客将会涉及：

1. remember函数：
   remember($a,$lat);将一个原子和一个列表lat作为参数，生成一个新的列表，新列表为移除了首个$a的列表。
   注：lat是每个单元为原子的数组。如有疑问，请看上篇文章——递归十诫之第一诫（预备式）的lat函数。
   这个函数还是有点实用价值的，假如想移除一个列表的首个某个原子，可以使用这个函数。
2. 快速排序的代码片段。

在此之前先定义一些名词：

剩余列表： 被移除第一个单元的列表。
例如：

$lat = ['a','b','c'];
$car = array_shift($lat);
此时的$lat=['b','c'];是原列表['a','b','c']的剩余列表

需要用到的知识点：array_merge函数。

$a1=array("red","green");
$a2=array("blue","yellow");
print_r(array_merge($a1,$a2));
// Array ( [0] => red [1] => green [2] => blue [3] => yellow )

一、 remember函数。

我们先来根据这个函数的输入与输出来看一下这个函数的具体功能。

在写代码前先来分析一下：

1. 先来看最简单的一种情况：假如一个列表是空列表，没有任何元素，那么$a永远都不可能是$lat的成员，所以直接返回[ ]。与上表中的序号1的输入输出相符。
   代码片段：

   if(empty($lat)){
    return [];
   }

2. 再来看相对简单的一种情况：假如$a是$lat的第一个元素，那么可以直接使用array_shift()函数，并且返回剩余列表即可。正如上表中的序号4一样。
   代码片段：

   $car = array_shift($lat);
   return $lat;

3. 最后来看一下比较头疼的情况：假如$a是$lat的第三个元素。以序号2为例：

   $a='c',$lat=['a','b','c','d']

有了前面的分析，我们就会想要是$a=’c’是列表的第一个成员就好啊。
按照这个思路往下走，发现只要对$lat使用几次array_shift()函数就可以实现$a为列表的第一个成员。只不过这个列表是[‘c’,’d’]。
目的是实现了，但是我们很快就会意识到几个问题：
Q1. 使用几次array_shift()函数？
使用几次我不知道，在这个例子中只要使用两次就可了，但是其他例子呢？$a在$lat中的位置是不确定的。（先假设$lat中有$a）。
但是好在我们知道该什么时候停止使用array_shift()函数：当$car=array_shift($lat)的值等于$a的时候就停止。
代码片段：

$car = array_shift($lat);
if ($a == $car) {
    return $lat;
}

Q2. 结果与序号2中的输出不符：
使用几次array_shift()函数之后，我们达到了$a=’c’成为列表[‘c’,’d’]的首个成员的目标，这样就变成了相对简单的情况。
但是如果按照相对简单的情况处理，我们将得到[‘d’]，而不是[‘a’,’b’,’d’]。对比发现：列表[‘a’,’b’,’c’,’d’]中’c’元素前面的所有成员都丢失了。
换句话说，我们只要保存’c’元素前面的所有的成员就可以得到相同的输出。那么该怎么保存呢？这就涉及到这篇博客的主题了：
用array_merge函数来构建数组。
代码片段：

return array_merge([$car],remember($a,$lat));
// 当前函数的参数之一的列表的第一个成员\$car与下一个函数调用的结果合并，这样就将\$car保留住了。

虽然我们现在还不知道这个函数完整的代码，但是我们知道什么时候归，前面分析了：当lat的值为['c','d']（因为此时的\$car='c'等于\$a）的时候就停止，而且返回的值为[‘d’]，即remember(‘c’,[‘c’,’d’])的值为[‘d’]。
栈如下：

array_merge(
    ['a'],
    array_merge(
        ['b'],
        remember('c',['c','d'])
        )
    );
其中remember('c',['c','d'])的值为['d'],故最终的返回结果为['a','b','d'];与序号2的输出相符。

完整代码如下：

function remember($a,$lat){
    if(empty($lat)){
        return [];
    }
    $car = array_shift($lat);
    if ($a == $car) {
        return $lat;
    }else{
        return array_merge([$car],remember($a,$lat));
    }
}

过程：

问题转换：
这样我们就成功地将移除列表中的首个某个成员的问题转换成了移除列表的首个成员的问题。（如果该列表的首个成员和$a相等的话）。

二、 快速排序的代码片段：

快速排序的返回值的代码如下：

 return array_merge(quick_sort($loe),array($pivot_key=>$pivot),quick_sort($gt));

在这里，也用到了第二诫——用array_merge函数来构建数组。

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