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;
}

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