登录  /  注册
php - 递归和循环最本质的区别是什么
PHPz
PHPz 2017-04-10 16:45:44
[PHP讨论组]
 public function noLimitCategory($categories,$top_id=0,$level=0){
             static $arr=array();
            //遍历数组
            foreach($categories as $category){
                //当前层级的分类数
                $category['level']=$level;
                if($category['parent_id']==$top_id){
                    $arr[]=$category;
                    $this->noLimitCategory($categories,$category['id'],$level+1);//递归
                }
            }
            //echo '<pre>';
            //var_dump($categories);exit;
            return $arr;
         }

递归和循环最本质的的区别是什么?比如上面的递归,每次递归都新开辟一个作用域吗,也就是说,这里的$level+1每次其实都是0+1对吧

PHPz
PHPz

学习是最好的投资!

全部回复(11)
PHPz

从功能上来说,所有用递归实现的都可以用循环实现,只不过有时候递归实现方便一些,从效率上说,循环一般都是大于递归的。

如楼主所说,每次递归都是创建一个新的作用域,而level其实在不同的作用域中的,每个 level都是上一级作用域的level+1,每次level都是不同的,所以不是0+1,这些level是不同的变量,虽然他们只是同名的不同变量。
写个循环版给你,没有优化,level可以不是数组,为了让你弄清楚每次递归的level并不是同一个level而写的

 public function noLimitCategory($categories,$top_id=0,$level=0){
             static $arr=array(); // 这个static 可以不要,因为是不是递归
             $top_id = array();
             $level = array();

            $top_id[0] = 0;
            $level[0] = 0;
            $i = 0;
            do{ 
                foreach($categories as $category){
                    $category['level']=$level[$i];
                    if($category['parent_id']==$top_id[$i]){
                        $arr[]=$category;
                        $top_id[] = category['id'];
                        $level[] = $level[$i] + 1;
                    }
                }
                $i++;
            }while($i<count(top_id))
            //echo '<pre>';
            //var_dump($categories);exit;
            return $arr;
         }

可见,如果写成循环,需要自己保存或是区分top_idlevel,而递归的话是在不同的作用域里面,所以暗含是指不同的top_idlevel

我们所说的递归效率低是说,每次函数调用,我们不仅仅需要多创建一个top_idlevel(上面的循环就是只是多创建了几个top_idlevel),而且要有其他地方保存每一次函数调用的返回地址和复制一次categories 的引用。另外我说过了,在循环中level是可以不作为数组的,所以其实只是需要多分配保存top_id的空间。因此,循环效率高于递归。

递归本质上是使用编译器提供的栈来实现这个算法,所以如果写成循环的形式需要自己维护这个栈的结构,并且在此基础上把不需要的东西都优化掉(一定可以优化掉的是函数的返回地址),就会得到一个等价的循环版。另外,不是所有的程序使用栈效率最高,而该写成循环就可以使用其他的数据结构达到优化的目的。问题就是循环需要自己维护一个栈(在某些情况下可以优化掉这个栈),所以代码就复杂了。

对于一般人来说,一旦学会了递归,遇到稍微复杂一点儿的贪心算法,动态规划或是遍历等问题,那么最容易想到的就是递归。从这个角度来说递归程序更简单(简单就是大家都能想到的意思)。

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号