递归和循环最本质的区别是什么
<code> 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 class="brush:php;toolbar:false">'; //var_dump($categories);exit; return $arr; }
递归和循环最本质的的区别是什么?比如上面的递归,每次递归都新开辟一个作用域吗,也就是说,这里的$level+1每次其实都是0+1对吧
回复内容:
<code> 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 class="brush:php;toolbar:false">'; //var_dump($categories);exit; return $arr; }
递归和循环最本质的的区别是什么?比如上面的递归,每次递归都新开辟一个作用域吗,也就是说,这里的$level+1每次其实都是0+1对吧
从功能上来说,所有用递归实现的都可以用循环实现,只不过有时候递归实现方便一些,从效率上说,循环一般都是大于递归的。
如楼主所说,每次递归都是创建一个新的作用域,而level
其实在不同的作用域中的,每个 level
都是上一级作用域的level+1
,每次level
都是不同的,所以不是0+1
,这些level
是不同的变量,虽然他们只是同名的不同变量。
写个循环版给你,没有优化,level
可以不是数组,为了让你弄清楚每次递归的level
并不是同一个level
而写的
<code> 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>'; //var_dump($categories);exit; return $arr; }</count></code>
可见,如果写成循环,需要自己保存或是区分top_id
和level
,而递归的话是在不同的作用域里面,所以暗含是指不同的top_id
和level
。
我们所说的递归效率低是说,每次函数调用,我们不仅仅需要多创建一个top_id
和level
(上面的循环就是只是多创建了几个top_id
和level
),而且要有其他地方保存每一次函数调用的返回地址和复制一次categories
的引用。另外我说过了,在循环中level
是可以不作为数组的,所以其实只是需要多分配保存top_id
的空间。因此,循环效率高于递归。
递归本质上是使用编译器提供的栈来实现这个算法,所以如果写成循环的形式需要自己维护这个栈的结构,并且在此基础上把不需要的东西都优化掉(一定可以优化掉的是函数的返回地址),就会得到一个等价的循环版。另外,不是所有的程序使用栈效率最高,而该写成循环就可以使用其他的数据结构达到优化的目的。问题就是循环需要自己维护一个栈(在某些情况下可以优化掉这个栈),所以代码就复杂了。
对于一般人来说,一旦学会了递归,遇到稍微复杂一点儿的贪心算法,动态规划或是遍历等问题,那么最容易想到的就是递归。从这个角度来说递归程序更简单(简单就是大家都能想到的意思)。
循环:块级别的自我重复。
递归:函数级别的自我重复。
再本质一点就是:
循环:jmp, jmp, jmp...
递归:push, push, push...pop, pop, pop...
所以递归太深了会StackOverflow。
递归,每次都会调用一次自身(跟平时调用没有什么区别),而调用函数的话,会把调用的函数压入执行栈,所以如果递归没有返回条件的话,栈会越来越高,最终会导致栈溢出。
而循环就是多次执行一系列的操作,完全可以把多次执行按照顺序一一写下来。
例如:
<code>var arr = [1,2,3]; // 定义一个数组 for(var i = 0;i<arr.length console.log></arr.length></code>
相当于:
<code>console.log(arr[0]); console.log(arr[1]); console.log(arr[2]);</code>
递归会多次调用函数,每次函数调用都会产生一个栈帧(C中叫栈帧,这里应该是作用域),循环则没有。
我感觉题主自己说得好像挺对的,作用域应该是一个关键,但是说只有作用域的话,又好像缺点什么,缺点啥,我说不上来。
拿排序来说,一般排序诸如冒泡插排,用的是循环吧,执行完了上一步,才循环进入下一步。
而文艺排序比如快排,用的是递归,我能把我排序的本身一而二,二而四,四而八。。。
从这个角度看,循环只能串行,递归还能有并行的性能。
数据结构
递归:栈
循环:列表
递归调用函数本身,而循环不会。
如果要处理的问题的深度不大,我认为递归和迭代的效率差不多。递归是消费栈空间,先递推(压栈)然后回归(逐步释放占用的栈),如果递归的深度比较大的话会很消耗内存,如果没有终止条件会导致栈溢出。而迭代重复执行一些步骤,执行完的就释放空间,一直到一个终止条件,所以迭代的空间复杂度应该低一些。一般很明确迭代终止的条件,我认为尽量使用迭代,但像树遍历这种很难知道迭代终止的条件,只能用递推逐步逼近,回归的方法去做。
循环是jmp 递归是push/pop
循环的结构是list,而递归是tree
大神你的qq是多少啊

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

PHP 8.4 带来了多项新功能、安全性改进和性能改进,同时弃用和删除了大量功能。 本指南介绍了如何在 Ubuntu、Debian 或其衍生版本上安装 PHP 8.4 或升级到 PHP 8.4

如果您是一位经验丰富的 PHP 开发人员,您可能会感觉您已经在那里并且已经完成了。您已经开发了大量的应用程序,调试了数百万行代码,并调整了一堆脚本来实现操作

Visual Studio Code,也称为 VS Code,是一个免费的源代码编辑器 - 或集成开发环境 (IDE) - 可用于所有主要操作系统。 VS Code 拥有针对多种编程语言的大量扩展,可以轻松编写

JWT是一种基于JSON的开放标准,用于在各方之间安全地传输信息,主要用于身份验证和信息交换。1.JWT由Header、Payload和Signature三部分组成。2.JWT的工作原理包括生成JWT、验证JWT和解析Payload三个步骤。3.在PHP中使用JWT进行身份验证时,可以生成和验证JWT,并在高级用法中包含用户角色和权限信息。4.常见错误包括签名验证失败、令牌过期和Payload过大,调试技巧包括使用调试工具和日志记录。5.性能优化和最佳实践包括使用合适的签名算法、合理设置有效期、

字符串是由字符组成的序列,包括字母、数字和符号。本教程将学习如何使用不同的方法在PHP中计算给定字符串中元音的数量。英语中的元音是a、e、i、o、u,它们可以是大写或小写。 什么是元音? 元音是代表特定语音的字母字符。英语中共有五个元音,包括大写和小写: a, e, i, o, u 示例 1 输入:字符串 = "Tutorialspoint" 输出:6 解释 字符串 "Tutorialspoint" 中的元音是 u、o、i、a、o、i。总共有 6 个元

本教程演示了如何使用PHP有效地处理XML文档。 XML(可扩展的标记语言)是一种用于人类可读性和机器解析的多功能文本标记语言。它通常用于数据存储

静态绑定(static::)在PHP中实现晚期静态绑定(LSB),允许在静态上下文中引用调用类而非定义类。1)解析过程在运行时进行,2)在继承关系中向上查找调用类,3)可能带来性能开销。

PHP的魔法方法有哪些?PHP的魔法方法包括:1.\_\_construct,用于初始化对象;2.\_\_destruct,用于清理资源;3.\_\_call,处理不存在的方法调用;4.\_\_get,实现动态属性访问;5.\_\_set,实现动态属性设置。这些方法在特定情况下自动调用,提升代码的灵活性和效率。
