資訊專欄INFORMATION COLUMN
摘要：貌似大部分語言中的遞歸都差不多，之所以在標(biāo)題加是因為搜了下后感覺網(wǎng)上用來描述這概念的不多，簡單地說遞歸就是函數(shù)調(diào)用自己的過程。
貌似大部分語言中的遞歸都差不多， 之所以在標(biāo)題加JS是因為搜了下后感覺網(wǎng)上用js來描述這概念的不多， 簡單地說遞歸就是函數(shù)調(diào)用自己的過程。下面的栗子可以很直觀地展示遞歸的執(zhí)行過程：
function rec(x){
if(x!==1){
console.log(x)
rec(x-1)
console.log(x)
}
}
rec(5) //輸出為5 4 3 2 2 3 4 5
由這個栗子?可知：在遞歸調(diào)用語句前的語句執(zhí)行是正常順序， 但是遞歸調(diào)用語句后的執(zhí)行卻是相反的也就是說在遞歸還沒有完成時，函數(shù)的輸出結(jié)果暫時被掛起，因為一般在計算機中，是以棧的形式來實現(xiàn)遞歸，這個過程如下：
5 rec(4) //第一級 5 4 rec(3) //第二級 5 4 3 rec(2) //第三級 5 4 3 2 rec(1) //第四級 console.log() 2 3 4 5 //以出棧形式輸出結(jié)果
當(dāng)遞歸完成時， 執(zhí)行流開始處理上一級遞歸中的遞歸語句后面的語句， 在這里是輸出當(dāng)前變量console.log(x)
遞歸非常適用于相同函數(shù)不同參數(shù)的迭代循環(huán)。但是因為需要為每一級的遞歸開辟內(nèi)存所以遞歸的開銷相對來說蠻大的， 在很多編程的語言中,對于遞歸的開銷問題有個TCO優(yōu)化（Tail Call Optimization）戳這篇博客了解更多?[翻譯] JS的遞歸與TCO尾調(diào)用優(yōu)化
之所以想起碼這篇博客，是因為最近看《算法與數(shù)據(jù)結(jié)構(gòu)JavaScript描述》（請拉黑此書，bug極多，極不推薦）中使用遞歸遍歷二叉樹的算法挺繞的， 寫篇博客厘清下。
這里直接借用原書的代碼(有刪改)， 以二叉樹的的中序遍歷為例：
// 節(jié)點對象的構(gòu)造函數(shù)
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.data;
}
//二叉樹的構(gòu)造函數(shù)
function BST() {
this.root = null;
this.insert = insert;
this.inOrder = inOrder;
}
//插入方法
function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
}
else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;
if (current == null) {
parent.left = n;
break;
}
}
else {
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
//調(diào)用兩次遞歸遍歷二叉樹
function inOrder(node) {
if (!(node == null)) {
inOrder(node.left);
console.log(node.show() )
inOrder(node.right);
}
}
//將以下數(shù)據(jù)導(dǎo)入二叉樹
nums.insert(23)
nums.insert(45)
nums.insert(16)
nums.insert(37)
nums.insert(3)
nums.insert(99)
nums.insert(22)
//中序遍歷二叉樹
inOrder(nums.root)
/*
輸出結(jié)果為：
3
16
22
23
37
45
99
*/
在inOrder函數(shù)中使用了兩次遞歸，它的執(zhí)行順序是：沿左邊找到最小值3，第一次遞歸完成， 之前被掛起的語句開始以出棧的形式執(zhí)行，輸出無子節(jié)點的節(jié)點3，然后回到上一級遞歸，輸出其上一級遞歸中的節(jié)點16， 在節(jié)點16處， 存在子節(jié)點，于是執(zhí)行向右遞歸，執(zhí)行到無子節(jié)點的22，輸出22后返回到節(jié)點16 ， 執(zhí)行流繼續(xù)往回執(zhí)行， 執(zhí)行到根節(jié)點23，輸出23后又插入一次向右遞歸，右遞歸到45， 存在左子節(jié)點，執(zhí)行向左遞歸， 以此類推，就完成了這棵二叉樹的中序遍歷
附張遍歷順序示意圖：
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/86226.html
摘要：像剛才的這幅圖，就是二叉搜索樹。而我們本文要學(xué)習(xí)的內(nèi)容，就是如何寫一個二叉搜索樹。但在二叉搜索樹中，我們把節(jié)點成為鍵，這是術(shù)語。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法四二叉搜索樹 本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊列第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)...
摘要：二叉樹是數(shù)據(jù)結(jié)構(gòu)中很重要的結(jié)構(gòu)類型，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也是深入學(xué)習(xí)編程的必由之路，這里我們簡單介紹下我對于二叉樹的理解，水平有限，如有錯誤還請不吝賜教。 二叉樹是數(shù)據(jù)結(jié)構(gòu)中很重要的結(jié)構(gòu)類型，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也是深入學(xué)習(xí)編程的必由之路，這里我們簡單介紹下我對于二叉樹的理解，水平有限，如有錯誤還請不吝賜教。 首先照例定義一個二叉樹的節(jié)點類 class Node { private int ...
在之前的文章中我們有講過樹的相關(guān)知識，例如，樹的概念、深度優(yōu)先遍歷和廣度優(yōu)先遍歷。這篇文章講述了一個特殊的樹——二叉樹。 什么是二叉樹 二叉樹是每個節(jié)點最多只能有兩個子節(jié)點的樹，如下圖所示： 一個二叉樹具有以下幾個特質(zhì)： 要計算在每層有多少個點，可以依據(jù)公式2^(i-1)個(i是樹的第幾層)； 如果這顆二叉樹的深度為k，那二叉樹最多有2^k-1個節(jié)點； 在一個非空的二叉樹中，若使...
閱讀 3437·2021-10-11 11:06
閱讀 2212·2019-08-29 11:10
閱讀 1969·2019-08-26 18:18
閱讀 3280·2019-08-26 13:34
閱讀 1589·2019-08-23 16:45
閱讀 1064·2019-08-23 16:29
閱讀 2829·2019-08-23 13:11
閱讀 3264·2019-08-23 12:58
