php递归算法
我们都知道，编程有两大难点：指针和递归。这里说一说递归。
一、什么是递归函数呢？
递归函数就是直接或间接的自己调用自己的函数。一句话就是：“自己调用自己”。
二、什么时候使用递归呢？
当需要不断重复某一方法时，也就是有某种共同的规律，有如“以此类推”，“重复多次”等情景时。 巧用递算法能减少大量代码。
三、简单理解递归。
可以这样简单的理解递归：A让朋友B代购一本书，B没空，托其朋友C代购，C让逛街的D顺路带来，最后,书到了A手里。梳理一下，
开始是：A -> B -> C -> D ,到D就停止了，
返回是：D -> C -> B -> A。
递归必须要有一个明确的出口，像这里D买到书就是出口，如果没有出口，将陷入无限循环。下面举几个实际的递归例子：
1、斐波那契数列
斐波那契数列又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、......;表达式：f(n) = f(n -1) + f(n - 2)( f(0)=0,f(1)=1 )
问题：求f(10)的值。
一、非递归解法：
function f($n){
$a = 1;
$aa = 1;
$sum = '';
for($i = 3;$i <= $n;$i ++){
$sum = $a + $aa;
$a = $aa;
$aa = $sum;
}
return $sum;
}
echo f(10);//55
二、递归解法：
function f($n){
if($n == 1 || $n == 2){//这里是出口
return 1;
}
return f($n-1)+ f($n-2);
}
echo f(10);//55
当$n的值为3时，
f(3) = f(2) + f(1) = 2;
f(4) = f(3) + f(2) = 2 + 1 = 3;
.......
f(10) = f(9) + f(8)
这样找到出口后，值一层一层的网上传递，直到得到结果。
递归的两个关键是：出口和循环体。
2、无限极分类
一、无限极分类循环实现：
$tree = array();
$datas = array(
array('id'=>1,'name'=>'裤子','pid'=>0),
array('id'=>2,'name'=>'帽子','pid'=>0),
array('id'=>3,'name'=>'短裤','pid'=>1),
array('id'=>4,'name'=>'长裤','pid'=>1),
array('id'=>5,'name'=>'红帽','pid'=>2),
array('id'=>6,'name'=>'礼帽','pid'=>2),
array('id'=>7,'name'=>'黑色短裤','pid'=>3),
array('id'=>8,'name'=>'白色短裤','pid'=>3),
);
//将id作为键值
foreach($datas as $data){
$tree[$data['id']] = $data;
$tree[$data['id']]['children'] = array();
}
foreach($tree as $k => $v){
if($v['pid'] != 0){
$tree[$v['pid']]['children'][] = &$tree[$k];//这里是关键
if($tree[$k]['children'] == null ){//删除空子类
unset($tree[$k]['children']);
}
}
}
//删除多余节点
foreach($tree as $k => $v){
if($v['pid'] != 0){
unset($tree[$k]);
}
}
输出：
Array
(
[1] => Array
(
[id] => 1
[name] => 裤子
[pid] => 0
[children] => Array
(
[0] => Array
(
[id] => 3
[name] => 短裤
[pid] => 1
[children] => Array
(
[0] => Array
(
[id] => 7
[name] => 黑色短裤
[pid] => 3
)
[1] => Array
(
[id] => 8
[name] => 白色短裤
[pid] => 3
)
)
)
[1] => Array
(
[id] => 4
[name] => 长裤
[pid] => 1
)
)
)
[2] => Array
(
[id] => 2
[name] => 帽子
[pid] => 0
[children] => Array
(
[0] => Array
(
[id] => 5
[name] => 红帽
[pid] => 2
)
[1] => Array
(
[id] => 6
[name] => 礼帽
[pid] => 2
)
)
)
)
递归实现：
$tree= $datas;
function get_tree($data,$pid){
$tree = array();
foreach($data as $value){
if($value['pid'] == $pid){
$value['children'] = get_tree($data,$value['id']);
if($value['children'] == null){
unset($value['children']);
}
$tree[] = $value;
}
}
return $tree;
}
print_r(get_tree($tree,0));die;
