递归十诫之第三诫
递归十诫之第三诫: 构建一个数组的时候,描述第一个典型元素,之后array_merge该元素到一般性递归上。
上篇博客——递归十诫之第二诫说到:使用array_merge函数来构建数组。
本篇博客将会涉及:
firsts函数:
- 参数:函数以一个数组$l为参数,该数组要么为空列表,要么只包含非空数组。
这个函数的参数有点特殊,还是通过一些例子来分清哪些可以作为参数,哪些则不能,例子如下:
序号 | $l | 能否作为参数 | 原因 |
---|---|---|---|
1 | [ ] | 能 | 空数组可以作为参数 |
2 | [[‘a’,’b’],[‘c,’d’]] | 能 | 该数组只包含非空数组 |
3 | [[‘a’,’b’],’c,’d’] | 否 | 该数组包含了非数组’c’和’d’ |
3 | [[‘a’,’b’],[ ]] | 否 | 该数组包含了空数组[ ] |
- 功能:该函数构建出一个新列表,新列表中的每个元素由数组$l中每个数组的第一个单元组成。
实用性:这个函数的实用性较低,但是并不妨碍我们通过这个函数来认识递归的规律。
firsts函数:
我们先来根据这个函数的输入与输出来体验一下这个函数的具体功能。
序号 | 输入 | 输出 | 原因 |
---|---|---|---|
1 | [ ] | [ ] | 无需赘言 |
2 | [ [‘a’,’b’],[‘c’,’d’],[‘e’,’f’] ] | [‘a’,’c’,’e’] | 数组$l的第一个数组的第一个单元是’a’,第二个数组的第一个单元是’c’,第三个数组的第一个单元是’e’ |
3 | [ [‘a’,’b’],[‘c’],[‘d’,’e’] ] | [‘a’,’c’,’d’] | ‘a’是[‘a’,’b’]的第一个单元,’c’是[‘c’]的第一个单元,’d’是[‘d’,’e’]的第一个单元 |
4 | [ [ [‘a’,’b’],’c’ ],[‘e’,’f’],[ [‘g’],’h’] ] | [ [‘a’,’b’],’e’,[‘g’] ] | [‘a’,’b’]是[ [‘a’,’b’],’c’ ]的第一个单元,’e’是[‘e’,’f’]的第一个单元,[‘g’]是[ [‘g’],’h’]的第一个单元 |
进一步分析这个函数的输入与输出
- 当输入是[ ](空数组)时,返回的是[ ](空数组)。
- 当输入是只包含非空数组的数组时,返回的是
数组
。
还记得remember函数吗?当输出是数组时,我们是怎么构建数组的?
好像有点感觉了。
我们来尝试一下利用前面提到的两诫来写出基本的骨架。
- 还记得递归十诫之第一诫(预备式)吗?
把empty?放在诸问题之首。
代码片段:
if(empty($l)){
return ...;
}
- 还记得递归十诫之第二诫吗?
用array_merge构建数组。
代码片段:
array_merge(...,firsts(剩余列表));
基本骨架:
function firsts($l){
if(empty($l)){
// 由前面的分析可知,当$l是空数组时,即empty($l)为true时,返回空数组。
return [];
}
...
return array_merge(...,firsts(剩余列表));
}
那这个函数的剩余部分是什么呢?我们就得先来看一下这个函数的功能:
该函数构建出一个新列表,新列表中的每个元素由数组$l中每个数组的第一个单元组成。
怎么实现呢?
这就涉及到今天这篇博客的主题了:构建一个数组的时候,描述第一个典型元素,之后array_merge该元素到一般性递归上。
当$l = [ [‘a’,’b’],[‘c’],[‘d’,’e’] ]时,第一个典型元素是什么呢?是’a’。怎么描述’a’呢?’a’是$l的第一个单元的第一个单元。
$car = array_shift($l);
var_dump($car); // 输出:['a','b'];
$carCar = array_shift($car);
var_dump($carCar); // 输出:'a';
然后只要把第一个典型元素array_merge到一般性递归上就实现了该功能。
完整的代码如下:
function firsts($l){
if(empty($l)){
return [];
}else{
$car = array_shift($l);
return array_merge([array_shift($car)],firsts($l));
}
}
具体的过程,以[ [‘a’,’b’],[‘c’,’d’],[‘e’,’f’] ]为例:
步骤 | 递 | 函数调用 | return | 归 |
---|---|---|---|---|
1 | ↓ | firsts([ [‘a’,’b’],[‘c’,’d’],[‘e’,’f’] ]) | array_merge([array_shift([‘a’,’b’])],firsts([ [‘c’,’d’],[‘e’,’f’] ])) | 结果 |
2 | ↓ | firsts([ [‘c’,’d’],[‘e’,’f’] ]) | array_merge([array_shift([‘c’,’d’])],firsts([ [‘e’,’f’] ])) | ↑ |
3 | ↓ | firsts([ [‘e’,’f’] ]) | array_merge([array_shift([‘e’,’f’])],firsts([ ])) | ↑ |
4 | 终止 | firsts([ ]) | [ ] | ↑ |
如果我要写一个seconds($l)函数呢?
在这里,输入是[ [‘a’,’b’],[‘c’,’d’],[‘e’,’f’] ],输出是[‘b’,’d’,’f’]。
那典型元素是什么呢?该如何写这个函数呢?这个函数有什么局限呢?就留给读者自己思考了。
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: