目录
回复内容:
首页 后端开发 php教程 递归和循环最本质的区别是什么

递归和循环最本质的区别是什么

Jun 06, 2016 pm 08:18 PM
php

<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_idlevel,而递归的话是在不同的作用域里面,所以暗含是指不同的top_idlevel

我们所说的递归效率低是说,每次函数调用,我们不仅仅需要多创建一个top_idlevel(上面的循环就是只是多创建了几个top_idlevel),而且要有其他地方保存每一次函数调用的返回地址和复制一次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是多少啊

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

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

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 Dec 24, 2024 pm 04:42 PM

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

我后悔之前不知道的 7 个 PHP 函数 我后悔之前不知道的 7 个 PHP 函数 Nov 13, 2024 am 09:42 AM

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

如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 Dec 20, 2024 am 11:31 AM

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

在PHP API中说明JSON Web令牌(JWT)及其用例。 在PHP API中说明JSON Web令牌(JWT)及其用例。 Apr 05, 2025 am 12:04 AM

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

php程序在字符串中计数元音 php程序在字符串中计数元音 Feb 07, 2025 pm 12:12 PM

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

您如何在PHP中解析和处理HTML/XML? 您如何在PHP中解析和处理HTML/XML? Feb 07, 2025 am 11:57 AM

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

解释PHP中的晚期静态绑定(静态::)。 解释PHP中的晚期静态绑定(静态::)。 Apr 03, 2025 am 12:04 AM

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

什么是PHP魔术方法(__ -construct,__destruct,__call,__get,__ set等)并提供用例? 什么是PHP魔术方法(__ -construct,__destruct,__call,__get,__ set等)并提供用例? Apr 03, 2025 am 12:03 AM

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

See all articles