递归和循环最本质的区别是什么
<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是多少啊

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

PHP 8.4 membawa beberapa ciri baharu, peningkatan keselamatan dan peningkatan prestasi dengan jumlah penamatan dan penyingkiran ciri yang sihat. Panduan ini menerangkan cara memasang PHP 8.4 atau naik taraf kepada PHP 8.4 pada Ubuntu, Debian, atau terbitan mereka

Jika anda seorang pembangun PHP yang berpengalaman, anda mungkin merasakan bahawa anda telah berada di sana dan telah melakukannya. Anda telah membangunkan sejumlah besar aplikasi, menyahpenyahpepijat berjuta-juta baris kod dan mengubah suai sekumpulan skrip untuk mencapai op

Kod Visual Studio, juga dikenali sebagai Kod VS, ialah editor kod sumber percuma — atau persekitaran pembangunan bersepadu (IDE) — tersedia untuk semua sistem pengendalian utama. Dengan koleksi sambungan yang besar untuk banyak bahasa pengaturcaraan, Kod VS boleh menjadi c

JWT adalah standard terbuka berdasarkan JSON, yang digunakan untuk menghantar maklumat secara selamat antara pihak, terutamanya untuk pengesahan identiti dan pertukaran maklumat. 1. JWT terdiri daripada tiga bahagian: header, muatan dan tandatangan. 2. Prinsip kerja JWT termasuk tiga langkah: menjana JWT, mengesahkan JWT dan muatan parsing. 3. Apabila menggunakan JWT untuk pengesahan di PHP, JWT boleh dijana dan disahkan, dan peranan pengguna dan maklumat kebenaran boleh dimasukkan dalam penggunaan lanjutan. 4. Kesilapan umum termasuk kegagalan pengesahan tandatangan, tamat tempoh, dan muatan besar. Kemahiran penyahpepijatan termasuk menggunakan alat debugging dan pembalakan. 5. Pengoptimuman prestasi dan amalan terbaik termasuk menggunakan algoritma tandatangan yang sesuai, menetapkan tempoh kesahihan dengan munasabah,

Tutorial ini menunjukkan cara memproses dokumen XML dengan cekap menggunakan PHP. XML (bahasa markup extensible) adalah bahasa markup berasaskan teks yang serba boleh yang direka untuk pembacaan manusia dan parsing mesin. Ia biasanya digunakan untuk penyimpanan data

Rentetan adalah urutan aksara, termasuk huruf, nombor, dan simbol. Tutorial ini akan mempelajari cara mengira bilangan vokal dalam rentetan yang diberikan dalam PHP menggunakan kaedah yang berbeza. Vokal dalam bahasa Inggeris adalah a, e, i, o, u, dan mereka boleh menjadi huruf besar atau huruf kecil. Apa itu vokal? Vokal adalah watak abjad yang mewakili sebutan tertentu. Terdapat lima vokal dalam bahasa Inggeris, termasuk huruf besar dan huruf kecil: a, e, i, o, u Contoh 1 Input: String = "TutorialSpoint" Output: 6 menjelaskan Vokal dalam rentetan "TutorialSpoint" adalah u, o, i, a, o, i. Terdapat 6 yuan sebanyak 6

Mengikat statik (statik: :) Melaksanakan pengikatan statik lewat (LSB) dalam PHP, yang membolehkan kelas panggilan dirujuk dalam konteks statik dan bukannya menentukan kelas. 1) Proses parsing dilakukan pada masa runtime, 2) Cari kelas panggilan dalam hubungan warisan, 3) ia boleh membawa overhead prestasi.

Apakah kaedah sihir PHP? Kaedah sihir PHP termasuk: 1. \ _ \ _ Membina, digunakan untuk memulakan objek; 2. \ _ \ _ Destruct, digunakan untuk membersihkan sumber; 3. \ _ \ _ Call, mengendalikan panggilan kaedah yang tidak wujud; 4. \ _ \ _ Mendapatkan, melaksanakan akses atribut dinamik; 5. \ _ \ _ Set, melaksanakan tetapan atribut dinamik. Kaedah ini secara automatik dipanggil dalam situasi tertentu, meningkatkan fleksibiliti dan kecekapan kod.
