資訊專欄INFORMATION COLUMN
摘要：遞歸常見問題及解決方案警惕堆棧溢出可以聲明一個(gè)全局變量來控制遞歸的深度，從而避免堆棧溢出。文章輸出計(jì)劃數(shù)據(jù)結(jié)構(gòu)與算法之美的系列文章，堅(jiān)持天左右更新一篇，暫定計(jì)劃如下表。
前言
算法為王。
排序算法博大精深，前輩們用了數(shù)年甚至一輩子的心血研究出來的算法，更值得我們學(xué)習(xí)與推敲。
因?yàn)橹笠v有內(nèi)容和算法，其代碼的實(shí)現(xiàn)都要用到遞歸，所以，搞懂遞歸非常重要。
1. 定義方法或函數(shù)調(diào)用自身的方式稱為遞歸調(diào)用，調(diào)用稱為遞，返回稱為歸。
簡(jiǎn)單來說就是：自己調(diào)用自己。
現(xiàn)實(shí)例子：周末你帶著女朋友去電影院看電影，女朋友問你，咱們現(xiàn)在坐在第幾排啊 ？電影院里面太黑了，看不清，沒法數(shù)，現(xiàn)在你怎么辦 ？
于是你就問前面一排的人他是第幾排，你想只要在他的數(shù)字上加一，就知道自己在哪一排了。
但是，前面的人也看不清啊，所以他也問他前面的人。
就這樣一排一排往前問，直到問到第一排的人，說我在第一排，然后再這樣一排一排再把數(shù)字傳回來。
直到你前面的人告訴你他在哪一排，于是你就知道答案了。
基本上，所有的遞歸問題都可以用遞推公式來表示，比如:
f(n) = f(n-1) + 1; // 其中，f(1) = 1
f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排數(shù)，f(1) = 1 表示第一排的人知道自己在第一排。
有了這個(gè)遞推公式，我們就可以很輕松地將它改為遞歸代碼，如下：
function f(n) {
if (n == 1) return 1;
return f(n-1) + 1;
}
2. 為什么使用遞歸 ？遞歸的優(yōu)缺點(diǎn) ？
優(yōu)點(diǎn)：代碼的表達(dá)力很強(qiáng)，寫起來簡(jiǎn)潔。
缺點(diǎn)：空間復(fù)雜度高、有堆棧溢出風(fēng)險(xiǎn)、存在重復(fù)計(jì)算、過多的函數(shù)調(diào)用會(huì)耗時(shí)較多等問題。
3. 什么樣的問題可以用遞歸解決呢 ？一個(gè)問題只要同時(shí)滿足以下 3 個(gè)條件，就可以用遞歸來解決。
問題的解可以分解為幾個(gè)子問題的解。何為子問題 ？就是數(shù)據(jù)規(guī)模更小的問題。
比如，前面講的電影院的例子，你要知道，自己在哪一排的問題，可以分解為前一排的人在哪一排這樣一個(gè)子問題。
問題與子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
比如電影院那個(gè)例子，你求解自己在哪一排的思路，和前面一排人求解自己在哪一排的思路，是一模一樣的。
存在遞歸終止條件
比如電影院的例子，第一排的人不需要再繼續(xù)詢問任何人，就知道自己在哪一排，也就是 f(1) = 1，這就是遞歸的終止條件。
4. 遞歸常見問題及解決方案警惕堆棧溢出：可以聲明一個(gè)全局變量來控制遞歸的深度，從而避免堆棧溢出。
警惕重復(fù)計(jì)算：通過某種數(shù)據(jù)結(jié)構(gòu)來保存已經(jīng)求解過的值，從而避免重復(fù)計(jì)算。
5. 如何實(shí)現(xiàn)遞歸 ？1. 遞歸代碼編寫
寫遞歸代碼的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼。
2. 遞歸代碼理解
對(duì)于遞歸代碼，若試圖想清楚整個(gè)遞和歸的過程，實(shí)際上是進(jìn)入了一個(gè)思維誤區(qū)。
那該如何理解遞歸代碼呢 ？
如果一個(gè)問題 A 可以分解為若干個(gè)子問題 B、C、D，你可以假設(shè)子問題 B、C、D 已經(jīng)解決。
而且，你只需要思考問題 A 與子問題 B、C、D 兩層之間的關(guān)系即可，不需要一層層往下思考子問題與子子問題，子子問題與子子子問題之間的關(guān)系。
屏蔽掉遞歸細(xì)節(jié)，這樣子理解起來就簡(jiǎn)單多了。
因此，理解遞歸代碼，就把它抽象成一個(gè)遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個(gè)步驟。
6. 例子 1. 一個(gè)階乘的例子：function fact(num) {
if (num <= 1) {
return 1;
} else {
return num * fact(num - 1);
}
}
fact(3) // 結(jié)果為 6
以下代碼可導(dǎo)致出錯(cuò)：
var anotherFact = fact; fact = null; alert(antherFact(4)); //出錯(cuò)
由于 fact 已經(jīng)不是函數(shù)了，所以出錯(cuò)。
使用 arguments.callee
arguments.callee 是一個(gè)指向正在執(zhí)行的函數(shù)的指針，arguments.callee 返回正在被執(zhí)行的對(duì)現(xiàn)象。
新的函數(shù)為：
function fact(num){
if (num <= 1){
return 1;
}else{
return num * arguments.callee(num - 1); //此處更改了。
}
}
var anotherFact = fact;
fact = null;
alert(antherFact(4)); // 結(jié)果為 24
2. 再看一個(gè)多叉樹的例子
先看圖
葉子結(jié)點(diǎn)：就是深度為 0 的結(jié)點(diǎn)，也就是沒有孩子結(jié)點(diǎn)的結(jié)點(diǎn)，簡(jiǎn)單的說就是一個(gè)二叉樹任意一個(gè)分支上的終端節(jié)點(diǎn)。
數(shù)據(jù)結(jié)構(gòu)格式，參考如下代碼：
const json = {
name: "A",
children: [
{
name: "B",
children: [
{
name: "E",
},
{
name: "F",
},
{
name: "G",
}
]
},
{
name: "C",
children: [
{
name: "H"
}
]
},
{
name: "D",
children: [
{
name: "I",
},
{
name: "J",
}
]
}
]
}
我們?nèi)绾潍@取根節(jié)點(diǎn)的所有葉子節(jié)點(diǎn)個(gè)數(shù)呢 ？
遞歸代碼如下：
/**
* 獲取根節(jié)點(diǎn)的所有 葉子節(jié)點(diǎn) 個(gè)數(shù)
* @param {Object} json Object 對(duì)象
*/
function getLeafCountTree(json) {
if(!json.children){
return 1;
} else {
let leafCount = 0;
for(let i = 0 ; i < json.children.length ; i++){
// leafCount = leafCount + getLeafCountTree(json.children[i]);
leafCount = leafCount + arguments.callee(json.children[i]);
}
return leafCount;
}
}
遞歸遍歷是比較常用的方法，比如：省市區(qū)遍歷成樹、多叉樹、階乘等。
7. 文章輸出計(jì)劃JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 的系列文章，堅(jiān)持 3 - 7 天左右更新一篇，暫定計(jì)劃如下表。
| 標(biāo)題 | 鏈接 |
| :------ | :------ |
| 時(shí)間和空間復(fù)雜度 | https://github.com/biaochenxu... |
| 線性表（數(shù)組、鏈表、棧、隊(duì)列） | https://github.com/biaochenxu... |
| 實(shí)現(xiàn)一個(gè)前端路由，如何實(shí)現(xiàn)瀏覽器的前進(jìn)與后退 ？| https://github.com/biaochenxu... |
| 棧內(nèi)存與堆內(nèi)存 、淺拷貝與深拷貝 | https://github.com/biaochenxu... |
| 遞歸 | https://github.com/biaochenxu... |
| 非線性表（樹、堆） | 精彩待續(xù) |
| 冒泡排序 | 精彩待續(xù) |
| 插入排序 | 精彩待續(xù) |
| 選擇排序 | 精彩待續(xù) |
| 歸并排序 | 精彩待續(xù) |
| 快速排序 | 精彩待續(xù) |
| 計(jì)數(shù)排序 | 精彩待續(xù) |
| 基數(shù)排序 | 精彩待續(xù) |
| 桶排序 | 精彩待續(xù) |
| 希爾排序 | 精彩待續(xù) |
| 堆排序 | 精彩待續(xù) |
| 十大經(jīng)典排序匯總 | 精彩待續(xù) |
如果有錯(cuò)誤或者不嚴(yán)謹(jǐn)?shù)牡胤?，?qǐng)務(wù)必給予指正，十分感謝。8. 最后
文章可以轉(zhuǎn)載，但須注明作者及出處，需要轉(zhuǎn)載到公眾號(hào)的，喊我加下白名單就行了。
參考文章：
遞歸：如何用三行代碼找到“最終推薦人”？
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/105312.html
摘要：強(qiáng)烈推薦上值得前端學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與算法項(xiàng)目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數(shù)據(jù)結(jié)構(gòu)，提供進(jìn)一步閱讀的解釋和鏈接。數(shù)據(jù)結(jié)構(gòu)和算法必知必會(huì)的個(gè)代碼實(shí)現(xiàn)。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就算招式練的再花哨，終究成不了高手；只有內(nèi)功深厚者，前端之路才會(huì)走得...
摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。歸并排序是一種穩(wěn)定的排序方法。因此，快速排序并不穩(wěn)定。希爾排序思想先將整個(gè)待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，只有內(nèi)功深厚者，前端之路才...
摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。非線性表中的樹堆是干嘛用的其數(shù)據(jù)結(jié)構(gòu)是怎樣的希望大家?guī)е@兩個(gè)問題閱讀下文。其中，前中后序，表示的是節(jié)點(diǎn)與它的左右子樹節(jié)點(diǎn)遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，...
摘要：棧內(nèi)存與堆內(nèi)存淺拷貝與深拷貝，可以說是前端程序員的內(nèi)功，要知其然，知其所以然。棧內(nèi)存與堆內(nèi)存中的變量分為基本類型和引用類型。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言 想寫好前端，先練好內(nèi)功。 棧內(nèi)存與堆內(nèi)存 、淺拷貝與深拷貝，可以說是前端程序員的內(nèi)功，要知其然，知其所以然。 筆者寫的 JavaScrip...
摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。這應(yīng)該是目前較為簡(jiǎn)單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就...
閱讀 2268·2021-11-22 14:56
閱讀 10101·2021-09-08 10:45
閱讀 1985·2019-08-30 13:54
閱讀 2871·2019-08-29 16:54
閱讀 2012·2019-08-29 14:20
閱讀 1781·2019-08-29 12:25
閱讀 1859·2019-08-29 12:17
閱讀 1057·2019-08-23 18:29
