递归

PHP

什么是递归

概念: 程序调用自己的编程技巧称为递归.一个过程函数在其定义或说明中有直接或间接调用自身的一种方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的大型重复计算，大大地减少了程序的代码量。

递归的两个条件

• 递归出口(终止递归的条件)
• 递归表达式(规律)

循环与递归

循环是执行一段代码，仅仅参数不同。递归要调用自己。也就相当于循环就像在一个地方打转，而递归是一层一层进入，再按原路返回，虽然每一层都一样(参数逐渐再缩小)
循环都可以改写成递归，但有的递归不能改写成循环。

无限级分类

无level层级

<?php
$arr = 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),
);
function getTree($data,$pid){
    $list = array();
    foreach($data as $key => $value){
        if($value['pid'] == $pid){
            $value['son'] = getTree($data,$value['id']);
            $list[] = $value;
        }
    }
    return $list;
}
$a = getTree($arr,0);
echo "<pre/>";
var_dump($a);exit;

输出结果:

Array
(
    [0] => Array
        (
            [id] => 1
            [name] => 电脑
            [pid] => 0
            [son] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [name] => 笔记本
                            [pid] => 1
                            [son] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 7
                                            [name] => 超级本
                                            [pid] => 3
                                            [son] => Array
                                                (
                                                )
                                        )
                                    [1] => Array
                                        (
                                            [id] => 8
                                            [name] => 游戏本
                                            [pid] => 3
                                            [son] => Array
                                                (
                                                )
                                        )
                                )
                        )
                    [1] => Array
                        (
                            [id] => 4
                            [name] => 台式机
                            [pid] => 1
                            [son] => Array
                                (
                                )
                        )
                )
        )
    [1] => Array
        (
            [id] => 2
            [name] => 手机
            [pid] => 0
            [son] => Array
                (
                    [0] => Array
                        (
                            [id] => 5
                            [name] => 智能机
                            [pid] => 2
                            [son] => Array
                                (
                                )
                        )
                    [1] => Array
                        (
                            [id] => 6
                            [name] => 功能机
                            [pid] => 2
                            [son] => Array
                                (
                                )
                        )
                )
        )
)

有level层级

<?php
$arr = 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),
);
function getTree($data,$pid,$level){
    $list = array();
    foreach($data as $key => $value){
        if($value['pid'] == $pid){
            $value['level'] = $level;
            $value['son'] = getTree($data,$value['id'],$level+1);
            $list[] = $value;
        }
    }
    return $list;
}
$a = getTree($arr,0,0);
echo "<pre/>";
var_dump($a);exit;

输出结果:

Array
(
    [0] => Array
        (
            [id] => 1
            [name] => 电脑
            [pid] => 0
            [level] => 0
            [son] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [name] => 笔记本
                            [pid] => 1
                            [level] => 1
                            [son] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 7
                                            [name] => 超级本
                                            [pid] => 3
                                            [level] => 2
                                            [son] => Array
                                                (
                                                )
                                        )
                                    [1] => Array
                                        (
                                            [id] => 8
                                            [name] => 游戏本
                                            [pid] => 3
                                            [level] => 2
                                            [son] => Array
                                                (
                                                )
                                        )
                                )
                        )
                    [1] => Array
                        (
                            [id] => 4
                            [name] => 台式机
                            [pid] => 1
                            [level] => 1
                            [son] => Array
                                (
                                )
                        )
                )
        )
    [1] => Array
        (
            [id] => 2
            [name] => 手机
            [pid] => 0
            [level] => 0
            [son] => Array
                (
                    [0] => Array
                        (
                            [id] => 5
                            [name] => 智能机
                            [pid] => 2
                            [level] => 1
                            [son] => Array
                                (
                                )
                        )
                    [1] => Array
                        (
                            [id] => 6
                            [name] => 功能机
                            [pid] => 2
                            [level] => 1
                            [son] => Array
                                (
                                )
                        )
                )
        )
)

参考资料:
递归