search
HomeBackend DevelopmentPHP Tutorial递归和循环最本质的区别是什么

<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是多少啊

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
PHP: An Introduction to the Server-Side Scripting LanguagePHP: An Introduction to the Server-Side Scripting LanguageApr 16, 2025 am 12:18 AM

PHP is a server-side scripting language used for dynamic web development and server-side applications. 1.PHP is an interpreted language that does not require compilation and is suitable for rapid development. 2. PHP code is embedded in HTML, making it easy to develop web pages. 3. PHP processes server-side logic, generates HTML output, and supports user interaction and data processing. 4. PHP can interact with the database, process form submission, and execute server-side tasks.

PHP and the Web: Exploring its Long-Term ImpactPHP and the Web: Exploring its Long-Term ImpactApr 16, 2025 am 12:17 AM

PHP has shaped the network over the past few decades and will continue to play an important role in web development. 1) PHP originated in 1994 and has become the first choice for developers due to its ease of use and seamless integration with MySQL. 2) Its core functions include generating dynamic content and integrating with the database, allowing the website to be updated in real time and displayed in personalized manner. 3) The wide application and ecosystem of PHP have driven its long-term impact, but it also faces version updates and security challenges. 4) Performance improvements in recent years, such as the release of PHP7, enable it to compete with modern languages. 5) In the future, PHP needs to deal with new challenges such as containerization and microservices, but its flexibility and active community make it adaptable.

Why Use PHP? Advantages and Benefits ExplainedWhy Use PHP? Advantages and Benefits ExplainedApr 16, 2025 am 12:16 AM

The core benefits of PHP include ease of learning, strong web development support, rich libraries and frameworks, high performance and scalability, cross-platform compatibility, and cost-effectiveness. 1) Easy to learn and use, suitable for beginners; 2) Good integration with web servers and supports multiple databases; 3) Have powerful frameworks such as Laravel; 4) High performance can be achieved through optimization; 5) Support multiple operating systems; 6) Open source to reduce development costs.

Debunking the Myths: Is PHP Really a Dead Language?Debunking the Myths: Is PHP Really a Dead Language?Apr 16, 2025 am 12:15 AM

PHP is not dead. 1) The PHP community actively solves performance and security issues, and PHP7.x improves performance. 2) PHP is suitable for modern web development and is widely used in large websites. 3) PHP is easy to learn and the server performs well, but the type system is not as strict as static languages. 4) PHP is still important in the fields of content management and e-commerce, and the ecosystem continues to evolve. 5) Optimize performance through OPcache and APC, and use OOP and design patterns to improve code quality.

The PHP vs. Python Debate: Which is Better?The PHP vs. Python Debate: Which is Better?Apr 16, 2025 am 12:03 AM

PHP and Python have their own advantages and disadvantages, and the choice depends on the project requirements. 1) PHP is suitable for web development, easy to learn, rich community resources, but the syntax is not modern enough, and performance and security need to be paid attention to. 2) Python is suitable for data science and machine learning, with concise syntax and easy to learn, but there are bottlenecks in execution speed and memory management.

PHP's Purpose: Building Dynamic WebsitesPHP's Purpose: Building Dynamic WebsitesApr 15, 2025 am 12:18 AM

PHP is used to build dynamic websites, and its core functions include: 1. Generate dynamic content and generate web pages in real time by connecting with the database; 2. Process user interaction and form submissions, verify inputs and respond to operations; 3. Manage sessions and user authentication to provide a personalized experience; 4. Optimize performance and follow best practices to improve website efficiency and security.

PHP: Handling Databases and Server-Side LogicPHP: Handling Databases and Server-Side LogicApr 15, 2025 am 12:15 AM

PHP uses MySQLi and PDO extensions to interact in database operations and server-side logic processing, and processes server-side logic through functions such as session management. 1) Use MySQLi or PDO to connect to the database and execute SQL queries. 2) Handle HTTP requests and user status through session management and other functions. 3) Use transactions to ensure the atomicity of database operations. 4) Prevent SQL injection, use exception handling and closing connections for debugging. 5) Optimize performance through indexing and cache, write highly readable code and perform error handling.

How do you prevent SQL Injection in PHP? (Prepared statements, PDO)How do you prevent SQL Injection in PHP? (Prepared statements, PDO)Apr 15, 2025 am 12:15 AM

Using preprocessing statements and PDO in PHP can effectively prevent SQL injection attacks. 1) Use PDO to connect to the database and set the error mode. 2) Create preprocessing statements through the prepare method and pass data using placeholders and execute methods. 3) Process query results and ensure the security and performance of the code.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Chat Commands and How to Use Them
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)