无限递归 | 语法糖的博客

无线递归用到的地方还是蛮多的，如果是我们itbasic上的话，那就是部门之间的关系，支撑体系下面有战略中心，战略中心下面有数据部，如果设计数据表维持这之间的关系，还有bbs，如何维护评论之间的关系（其实像laravel的论坛，他的评论关系都是从上往下一条线的，只是在评论的开头有@人的标志，我们的论坛是分为1级评论和多级，除了1级之外的评论都是在1级评论的后面按照1条线排列，没有显示主从关系），当我们需要获取这个评论的顶级的时候，我们就需要用到无线递归的知识。

以部门举例，我们在使用的过程中，需要找到这个部门的相关父级部门（子孙树），或者我们需要知道某个部门是否属于某个部门，我们既可以用家谱树去实现，也可以用子孙树去实现，用子孙树去实现的一个好处就是，当我们知道父级节点，一次性求出这个父级节点的所有子孙，通过判断子节点是否在这个父级节点的子孙中，就能知道是否满足条件。但如果我们通过家谱树，我们需要每次根据子节点，去求一次家谱，然后来判断家谱树中是否有这个父级节点存在，来判断是否符合条件。

<?php

$address = array(
    array('id'=>1  , 'address'=>'安徽' , 'parent_id' => 0),
    array('id'=>2  , 'address'=>'江苏' , 'parent_id' => 0),
    array('id'=>3  , 'address'=>'合肥' , 'parent_id' => 1),
    array('id'=>4  , 'address'=>'庐阳区' , 'parent_id' => 3),
    array('id'=>5  , 'address'=>'大杨镇' , 'parent_id' => 4),
    array('id'=>6  , 'address'=>'南京' , 'parent_id' => 2),
    array('id'=>7  , 'address'=>'玄武区' , 'parent_id' => 6),
    array('id'=>8  , 'address'=>'梅园新村街道', 'parent_id' => 7),
    array('id'=>9  , 'address'=>'上海' , 'parent_id' => 0),
    array('id'=>10 , 'address'=>'黄浦区' , 'parent_id' => 9),
    array('id'=>11 , 'address'=>'外滩' , 'parent_id' => 10),
    array('id'=>12 , 'address'=>'安庆' , 'parent_id' => 1)
    );

function test($data, $pid)
{
    static $arr = [];
    foreach ($data as $key=>$value) {
        if ($value['id'] == $pid) {
            $arr[] = $value;
            test($data, $value['parent_id']);
        }
    }
    return $arr;
}

var_dump(test($address, 4));

// 上面方法在多次循环获取的时候因为static变量的原因会出现一直叠加的错误
// 下面是改进的方法

function test1($data, $pid, &$arr)
{
    
    foreach ($data as $key=>$value) {
        if ($value['id'] == $pid) {
            $arr[] = $value;
            test($data, $value['parent_id']);
        }
    }
    return $arr;
}

var_dump(test($address, 4, []));

庐阳区，合肥，安徽

子孙树的实现

function test1($data, $id, $level = 1， &$arr)
{
    
    foreach ($data as $key=>$value) {
        if ($value['parent_id'] == $id) {
            $value['level'] = $level;
            $arr[] = $value;
            test1($data, $value['id'], $level + 1);
        }
    }
    
}
//level主要用来显示是几级的儿子
// 上面这种方式其实不能实现层级结构，只能用level来表示，因为从开始往下面读的话，开始的数据先计算出来，是不能改变的，所以为了实现层级结构只能从后往前读
// 不借助 &$arr来实现
function children($id) {
  $self = self($id);
  $children = getChildrenByPid($self['id']);
  if ($children) {
  foreach($children as $value) {
  	$slef['children'][] = children($value['id']); // 这个地方很重要，如果想不出来的话，可当做是最后一层  a->a1,a2->a3, 我们怎么返回a这个node节点的结构
}
  
} else {
 $self['children'] = [];
}
return $self;
}

还记得我们在大学学习数据结构的时候，因为递归对于效率有影响，所以经常需要把递归改成迭代，上述家谱树容易修改，子孙树需要用到栈，自己不是很理解

// 家谱树递归的修改成普通方式
function test2($data, $pid， &$arr)
{
    while ($pid != 0) {
        foreach($data as $key=>$value) {
            if ($value['id'] == $pid) {
                $arr[] = $value;
                $pid = $value['parent_id'];
                break;
            }
        }
    }
    return $arr;
}
var_dump(test2($address, 4));
//迭代和递归的转换主要就是靠迭代找到那个停止往上找的条件
// 今天看了别人的代码 https://github.com/chenye2017/china-divisions
// 更加理解递归，我们只需要保存当前的状态并返回，可以不借助 &地址 符
function ancestors($id)
{
  $slef = self($id);  //获取自己信息
  if ($info) {
   $parent = ancesotrs($id);
   $parent[] = $self; // 保存当时环境(只需要考虑当前环境就好，不用考虑递归)，并传递给上一个调用者，用来叠加
   return $parent;
} else {
  return []; // 相当于
}
}

大致就是上面这些，像面包屑导航，不要看着从左到右，其实他也是一棵家谱树，因为他从始至终就只有一棵树。

还有就是移动各个部门位置问题：

想象一下，一棵树，我把某个分支截取下来放到另一个分支上是很正常的事情，但问题是有时候，我会出现把父亲节点的父亲设置成自己的子节点，这样树枝就断了，这样是不可取的，除此之外，任意移动都是可以的。