目次
回复内容:
ホームページ バックエンド開発 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 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

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 開発者であれば、すでにそこにいて、すでにそれを行っていると感じているかもしれません。あなたは、運用を達成するために、かなりの数のアプリケーションを開発し、数百万行のコードをデバッグし、大量のスクリプトを微調整してきました。

PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 Dec 20, 2024 am 11:31 AM

Visual Studio Code (VS Code とも呼ばれる) は、すべての主要なオペレーティング システムで利用できる無料のソース コード エディター (統合開発環境 (IDE)) です。 多くのプログラミング言語の拡張機能の大規模なコレクションを備えた VS Code は、

JSON Web Tokens(JWT)とPHP APIでのユースケースを説明してください。 JSON Web Tokens(JWT)とPHP APIでのユースケースを説明してください。 Apr 05, 2025 am 12:04 AM

JWTは、JSONに基づくオープン標準であり、主にアイデンティティ認証と情報交換のために、当事者間で情報を安全に送信するために使用されます。 1。JWTは、ヘッダー、ペイロード、署名の3つの部分で構成されています。 2。JWTの実用的な原則には、JWTの生成、JWTの検証、ペイロードの解析という3つのステップが含まれます。 3. PHPでの認証にJWTを使用する場合、JWTを生成および検証でき、ユーザーの役割と許可情報を高度な使用に含めることができます。 4.一般的なエラーには、署名検証障害、トークンの有効期限、およびペイロードが大きくなります。デバッグスキルには、デバッグツールの使用とロギングが含まれます。 5.パフォーマンスの最適化とベストプラクティスには、適切な署名アルゴリズムの使用、有効期間を合理的に設定することが含まれます。

母音を文字列にカウントするPHPプログラム 母音を文字列にカウントするPHPプログラム Feb 07, 2025 pm 12:12 PM

文字列は、文字、数字、シンボルを含む一連の文字です。このチュートリアルでは、さまざまな方法を使用してPHPの特定の文字列内の母音の数を計算する方法を学びます。英語の母音は、a、e、i、o、u、そしてそれらは大文字または小文字である可能性があります。 母音とは何ですか? 母音は、特定の発音を表すアルファベットのある文字です。大文字と小文字など、英語には5つの母音があります。 a、e、i、o、u 例1 入力:string = "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

静的結合(静的::) 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。\ _ \ _コンストラクト、オブジェクトの初期化に使用されます。 2。\ _ \ _リソースのクリーンアップに使用される破壊。 3。\ _ \ _呼び出し、存在しないメソッド呼び出しを処理します。 4。\ _ \ _ get、dynamic属性アクセスを実装します。 5。\ _ \ _セット、動的属性設定を実装します。これらの方法は、特定の状況で自動的に呼び出され、コードの柔軟性と効率を向上させます。

See all articles