PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死循环

递归在项目中用到比较多的地方是获取商品分类或者其他的分类,以及邀请人等等~还有一些比如阶乘,斐波那契数列,汉诺塔也用到了递归算法

首先来说说什么是无限极分类。按照我的理解,就是对数据完成多次分类,如同一棵树一样,从根开始,到主干、枝干、叶子,网络上很多无限级的分类,但无非是两种,一种是递归算法,一种是非递归算法

无限级分类是一种分类技巧,例如部门组织,文章分类,学科分类等常用到无限级分类,将其简单理解成分类就好了。其实我们仔细想一下,生活中的分类简直太多了,衣服可以分为男装和女装,也可以分为上衣和裤子,也可以根据年龄段分类

递归点:发现当前问题可以有解决当期问题的函数,去解决规模比当前小一点的问题来解决

递归出口:当问题解决的时候,已经到达(必须有)最优子问题,不能再次调用函数

如果一个函数递归调用自己而没有递归出口:就是死循环

递归的本质是函数调用函数,一个函数需要开辟一块内存空间,递归会出现同时调用N多个函数(自己),递归的本质是利用空间换时间

项目中需要获取分类或者查询用户邀请人的时候,一般都是直接将所有所有数据查出来,然后调用递归方法去实现逻辑,这样也节省了不少时间,也就是上面所说的空间换时间

这里用我在项目中做的一个查询某一用户的下级作为演示,表里存的数据一般都是在每一个用户的数据中加上一个inv_id

/**
 * 获取用户ID
 */
public function actionGetUserId()
{
    $model = new UserModel();
    $userInfo = $model::find()->where(['level'=> 13])->asArray()->all();
    $userId = $this->getInvId($userInfo,61);
    var_dump($userId);
}

接着调用有递归算法的方法

public function getInvId($data, $invId)
{
    static $arr = [];
    foreach ($data as $key => $val) {
        if ($val['inv_id'] == $invId) {
            $arr[] = $val['id'];
            $this->getInvId($data, $val['id']);
        }
    }
    return $arr;
}

递归另一个令人印象深刻的就是简单事情重复做。自上而下分解后,每一步是在更小规模上解决同一个模块化的问题,最终再以堆栈式的结构回溯

3 条评论

发表评论

*