递归算法引起的问题分析与解决

原文在我自己的博客里，小伙伴们也可以点击阅读原文跳转查看，还有好听的背景音乐~递归应该算是一个很编码算法中的常见事物。之前在学习C语言的时候，也学过一些基本的算法，比如Fibonacci。在学习的时候，我对算法的编程能力有一种强烈的敬畏感，因为我觉得懂算法的人很厉害，可以通过一个短的算法解决长的代码块，得到思路。期望的结果。今天在实际工作中也遇到了一些算法方面的问题。整理一下，形成今天的内容【算法中的递归算法】。什么是递归，借用百科全书中的一段话来表达：过程或函数在其定义或描述中有直接或间接调用自身的方法。递归的能力也引用了百科全书中的一句话，个人觉得很经典：用有限的句子来定义无限的对象集合；这句话是什么意思？通俗的理解，我只有一套程序，但是我可以使用递归（自调用自身）特性，不管你有多少个值，我都可以根据具体的程序给你妥善处理逻辑。（太强大了，嘿嘿！）我之前对递归的理解是调用自己，通过多次调用自己，用同样的程序方法来解决问题；这种方法可以显着减少代码量，并且灵活，尤其是有多个循环的时候，可以用递归代替。但是这种方法也有缺点，就是提高了程序的运行速度，有时可能会因为编码不当导致死循环、堆栈溢出等问题。但只要用得好，解决问题也不错；问题是今天在工作中，遇到一个无限分类的多维数组转成html树的问题时，遇到了一点小麻烦，可能是草草了事，当局者迷。正因为如此，我感觉自己陷入了一个死循环，无法自拔。后来咨询了身边的朋友才得以解决。我们来看看是哪里出了问题（其实顺丰社区上早就提过这个问题了，问题的标题是多维数组分类树组合html树的问题？（递归），有兴趣的朋友可以去看看）:数组结构初始数组结构是一个无限分类的多维数组：从上图可以看出，这个数组的childs下标对应的是子类，可以有无限类。我们要把它组装成如下图所示的理想形式：虽然看起来很简单，但实际上走了很多弯路，最后卡在一个点上一直没有出来。我最初的递归方法是：问题代码functioncreatHtmlTree($tree){//创建一个静态变量static$htmlTree;$htmlTree.='

';foreach($treeas$key=>$value){$htmlTree.="
• {$value['name']}去某个地方";if(isset($value['childs'])&&is_array($value['childs'])){//每次将结果添加到静态变量$html=creatHtmlTree($value['childs']);$htmlTree.=$html;}$htmlTree.="
";}$htmlTree.="

";return$htmlTree;}通过测试得到下图的错误内容：问题分析可以看出是给$htmlTree变量赋予了额外的值，求教一下明白了。在我的代码中，static$htmlTree;$htmlTree.='

';和$html在if=creatHtmlTree($value['childs']);$htmlTree.=$html;代码逻辑有问题。问题是由于$htmlTree设置为静态变量，在递归的每一次计算中，默认最终的计算结果已经给了$htmlTree，我在if中又把结果加进去了，所以导致了问题输出，那么如何改变呢？只需更改：$html=creatHtmlTree($value['childs']);$htmlTree.=$html;至：创造mlTree($value['childs']);就是这样，他可以在递归操作的时候通过$htmlTree.='
';$htmlTree.="
• {$value['name']}去某处";$htmlTree.="
";$htmlTree.="
";这四行代码可以为$htmlTree增加价值。我们来看看解决方案，看看最终形式的递归方法是什么样的：//递归操作创建一个html树结构functioncreatHtmlTree($tree){//声明一个静态变量static$htmlTree;$htmlTree.='
';foreach($treeas$key=>$value){//将值添加到静态$htmlTree变量$htmlTree.="
• {$value['name']}去某处";如果(isset($value['childs'])&&is_array($value['childs'])){creatHtmlTree($value['childs']);}$htmlTree.="
";}//分配ul结束标记$htmlTree.="
";return$htmlTree;}这样就可以解决了。还有一种方式，就是通过返回值来进行递归操作：$htmlTree.='
';foreach($treeas$key=>$value){//将值累加到变量$htmlTree$htmlTree.="
• {$value['name']}去某处";if(isset($value['childs'])&&is_array($value['childs'])){//每次递归的结果添加到$htmlTree$htmlTree.=creatHtmlTree($value['childs']);}$htmlTree.="
";}//赋值ul结束标记$htmlTree.="
";return$htmlTree;}通过这个返回值累加算法，也可以得到想要的结果。测试今天为了测试解决递归算法带来的问题，特地找了一段代码进行测试。也是我下午一直在试验的demo。手痒的可以复制到本地自己体验一下：1,'parentid'=>0,'name'=>'China'],['id'=>2,'parentid'=>0,'name'=>'美国'],['id'=>3,'parentid'=>0,'name'=>'韩国'],['id'=>4,'parentid'=>1,'name'=>'北京'],['id'=>5,'parentid'=>1,'name'=>'上海'],['id'=>6,'parentid'=>1,'name'=>'广西'],['id'=>7,'parentid'=>6,'name'=>'桂林'],['id'=>8,'parentid'=>6,'name'=>'南宁'],['id'=>9,'parentid'=>6,'name'=>'柳州'],['id'=>10,'parentid'=>2,'name'=>'纽约'],['id'=>11,'parentid'=>2,'name'=>'华盛顿'],['id'=>12,'parentid'=>3,'name'=>'首尔'],];/**格式化数组输出**/functionp($arr){echo"

";echo'=========================开始=========================';回声“
”；如果($arr){print_r($arr);}else{echo'值为空';}回声“
”；echo'=========================结束=========================';echo"

";}/***多维数组树结构*/functiontree($data,$pid=0){$children=[];foreach($dataas$key=>$value){if($value['parentid']==$pid){$children[]=$value;}}if(empty($children)){返回null；}foreach($childrenas$key=>$value){$chid=tree($data,$value['id']);如果($chid!=null){$children[$key]['childs']=$chid;}}return$children;}//递归操作创建html树结构functioncreatHtmlTree($tree){//$htmlTree是一个普通的局部变量；$htmlTree.='
';foreach($treeas$key=>$value){//将值累加到$htmlTree变量$htmlTree.="
• {$value['name']}去某处";if(isset($value['childs'])&&is_array($value['childs'])){//每次递归的结果累加到$htmlTree$htmlTree.=creatHtmlTree($value['childs']);}$htmlTree.="
";}//分配ul结束标记$htmlTree.="
";返回$htmlTree;}$tree=tree($data);$htmlTree=creatHtmlTree($tree);p($tree);p($htmlTree);总结一下算法，这个技术是我向往的高级东西，觉得很炫。开头提到了复杂的业务程序可以用极短的代码来解决，大大减少代码量。但它也充满了威胁，就像一颗无形的炸弹。所以在后面的递归算法中，要注意避免出现问题。好了，以上就是今天的全部内容。补充一下百科上看到的递归解释的两句话，也很经典，这里是：递归需要边界条件，递归前向段和递归返回段。当不满足边界条件时，递归前进；当满足边界条件时，递归返回这大概是指递归的运行条件。超过。