递归十诫之第四诫（预备式）上

递归十诫之第四诫（预备式）上：

1. 在递归时总是至少改变一个参数。
2. 该参数必须向着不断接近结束条件的方向而改变。
3. 改变的参数必须在结束条件中得以测试：剩余数组作为递归的参数时，用 empty? 测试是否结束。
   上篇博客——递归十诫之第三诫说到：当构建一个数组时，描述第一个典型元素，之后 array_merge 该元素到一般性递归上。

本篇博客将会涉及：

1. insertL函数

• 语法：insertL($new,$old,$lat);
• 参数：
  • 原子$new。
  • 原子$old。
  • 一个一维数组$lat。
• 功能：insertL函数在$lat的第一个$old的前面（左边）添加$new。
• 返回值：新的数组。

2. insertR函数：

• 语法：insertR($new,$old,$lat);
• 参数：
  • 原子$new。
  • 原子$old。
  • 一个一维数组$lat。
• 功能：insertR函数在$lat的第一个$old的后面（右边）添加$new。
• 返回值：新的数组。

3. subst函数

• 语法：subst($new,$old,$lat);
• 参数：
  • 原子$new。
  • 原子$old。
  • 一个一维数组$lat。
• 功能：subst函数用$new替换$lat的第一个$old。
• 返回值：新的数组。
• 注：subst为substitute的前五个字母，意为替换的意思。

本篇博客的重点

虽然这篇博客有三个函数，但是只要把其中的任意一个函数搞明白了，其他的两个函数都可以触类旁通。考虑到文章篇幅问题，今天这篇博客的重点就放在梳理 insertL 函数上。

一、insertL 函数：

老规矩，还是先通过输入与输出来体验一下该函数的具体功能：

这个函数的参数和功能都很好理解，就不再赘述了。

来看看具体是怎么实现的吧。
insertL函数的输出是什么呢？是数组。
在第三诫中我们提到，当构建一个数组，描述第一个典型元素，之后array_merge该元素到一般性递归上。
在这里，第一个典型元素是什么？就是数组的第一个元素，很普通。
在这里，一般性递归是什么呢？和前面博客中的函数一样，只要改变$lat参数即可。一般性递归如下：

insertL($new,$old,剩余数组);

与今天这篇博客的主题一致：在递归时总是至少改变一个参数。

有了前面三篇博客的基础，很快就能写出insertL函数的基本骨架：

function insertL($new,$old,$lat){
    if(empty($lat)){
        return [];
    }
    ...
    array_merge([第一个典型元素],insertL($new,$old,剩余数组));
}

剩余部分怎么写呢？
还是得回到insertL函数的功能来：
在$lat的第一个$old的前面（左边）添加$new。
怎么实现呢？在此之前，我们先来回忆一下remember函数是怎么移除$lat中的首个$a的。remember函数的完整代码：

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));
    }
}

判断$lat的第一个元素是否和$a相等：

1. 如果不相等，就把该元素保存起来，对剩余数组进行递归，直至$lat变为空数组；
2. 如果相等，就直接返回剩余数组。
   为什么能移除首个$a呢？当$lat的第一个元素与$a相等时，并没有保存$a，而是直接返回剩余数组。

insertL函数的实现和remember函数的实现有异曲同工之妙：
判断$lat的第一个元素是否和$old相等：

1. 如果不相等，就把该元素保存起来，对剩余数组进行递归，直至$lat变为空数组；
2. 如果相等，依次合并$new,$old,剩余数组。返回得到的新数组。
   完整代码：

   function insertL($new,$old,$lat){
    if (empty($lat)) {
        return [];
    }
    $car = array_shift($lat);
    if ($old == $car) {
        return array_merge([$new],array_merge([$old],$lat));
    }else{
        return array_merge([$car],insertL($new,$old,$lat));
    }
   }

二、insertR 函数

insertR 函数的功能：在$lat的第一个$old的后面（右边）添加$new。功能和insertL几乎一样。只不过当$lat的第一个元素等于$old时，需要调整一下合并的顺序——依次合并$old,$new,剩余列表。
完整代码如下：

function insertL($new,$old,$lat){
    if (empty($lat)) {
        return [];
    }
    $car = array_shift($lat);
    if ($old == $car) {
        // 和insertL函数的区别就在这行。
        return array_merge([$old],array_merge([$new],$lat));
    }else{
        return array_merge([$car],insertL($new,$old,$lat));
    }
}

三、subst函数

subst函数功能：用$new替换$lat的第一个$old。
既然是替换，说明没有保存$old，而是保存了$new。过程和上面两个函数类似，就不再赘述了。
完整代码如下：

function insertL($new,$old,$lat){
    if (empty($lat)) {
        return [];
    }
    $car = array_shift($lat);
    if ($old == $car) {
        return array_merge([$new],$lat);
    }else{
        return array_merge([$car],insertL($new,$old,$lat));
    }
}

对比上面四个函数发现，结构类似，只是返回值不一样，就得到了功能各异的函数。

这一诫还没完，总结就先不写了，留到第四诫（预备式）下来写。

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