框架设计中递归树的浅谈与实例

递归是一种函数调用自身的机制，必须有边界条件退出递归。常见用于无限极分类、目录的递归访问、二分查找和合并排序等。

递归需满足的三要素

1、一个问题可以分解为几个子问题的解。

2、这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一致。

3、存在递归终止条件。

三种常用方式：

1. 使用 "引用" 即使用"&"符号，意思为将内部的$result函数内容在满足条件场景下重复调用本身函数，将各内部$result函数反哺给最开始的内部$result函数,常以"递归树"形式展开。

/**

 * @param int $a 递增的数值

 * @param array $result

 */

function test($a=0,&$result=array()){

$a++;

if ($a<10) { //场景判断

$result[]=$a; //内部$result函数

test($a,$result); //满足条件，修改参数，准备进入下层调用(重复调用,且内部$result会累加)

}

return $result;

}

2. 使用 全局变量 global

  global在函数内申明变量是外部变量的同名引用。

/**

 * @param int $a 递增的数值

 * @param array $result 外部result

 */

function test($a=0,$result=array()){

global $result; //外部$result变量

$a++;

if ($a<10) {

$result[]=$a;

test($a,$result);

}

return $result;

}

3. 静态变量

/**

 * @param int $a 递增的数值

 */

function test($a=0){

static $result=array(); //仅在第一次调用函数的时候对变量进行初始化，并且保留变量值

$a++;

if ($a<10) {

$result[]=$a;

test($a);

}

return $result;

}

PHP内置的与递归行为有关的函数有array_merge_recursive,array_walk_recursive,array_replace_recursive等

深层次

跟递归有关的另一个重要的概念是栈。栈的特点是“后进先出”，也就是最后压入的元素有最高的优先权，每次压入数据时，栈层层向上叠放，而取数据时，则是从栈顶取出需要的数据。