JavaScript的遞歸之遞歸與循環(huán)示例介紹
更新時間：2013年08月05日 17:09:28 作者：
對于不同類型的需要重復(fù)計算的問題，循環(huán)和遞歸兩種方法各有所長，能給出更直觀簡單的方案，下面為大家詳細的介紹下JavaScript的遞歸與循環(huán)，感興趣的朋友可以了解下
遞歸與循環(huán)
對于不同類型的需要重復(fù)計算的問題，循環(huán)和遞歸兩種方法各有所長，能給出更直觀簡單的方案。另一方面，循環(huán)和遞歸的方法可以互相轉(zhuǎn)換。任何一個循環(huán)的代碼都可以用遞歸改寫，實現(xiàn)相同的功能；反之亦然。在不失去其普遍性的前提下，可以把循環(huán)和遞歸分別用下列偽代碼概括。
偽代碼格式說明：循環(huán)采用while形式；變量不加定義；賦值用:=；條件表達式和執(zhí)行的語句都寫成函數(shù)的形式，圓括號內(nèi)寫上相關(guān)的值。其他語法方面，盡量接近Javascript的規(guī)范。
//pseudo code of a loop
//while形式
function loop(arguments){
//結(jié)果的初始值
result:=initial_value;
while(condition(variable, arguments)){//循環(huán)條件，可能只需arguments，也可能為了方便引入循環(huán)變量
//計算結(jié)果。參數(shù)包括之前的結(jié)果、當(dāng)前循環(huán)變量和外部變量
result:=calculate(result, variable, extern_variables);
//影響函數(shù)的外部環(huán)境，即修改外部變量
changeStatus(result, variable, extern_variables);
//執(zhí)行完循環(huán)體中的語句后，修改參數(shù)或循環(huán)變量。
modify_arguments_variable(arguments, variable);
}
//返回結(jié)果
return result;
}
同樣我們給出遞歸函數(shù)的偽代碼。
//pseudo code of a recursion
function recursion(arguments){
//以下代碼為控制函數(shù)重復(fù)調(diào)用的結(jié)構(gòu)部分。
//獲得再次調(diào)用此函數(shù)的新的參數(shù)，可能為多組arguments值。
//對應(yīng)于循環(huán)中的condition(variable, arguments)和modify_arguments_variable(arguments, variable)。
new_arguments:=conditional_get_next(arguments);
//對新參數(shù)的每一組，調(diào)用函數(shù)自身。
results:=recursion(new_arguments);
//以下的代碼為每次調(diào)用都運行的功能部分
//計算結(jié)果。涉及到之前的結(jié)果、當(dāng)前循環(huán)變量和外部變量。
//對應(yīng)于循環(huán)中的result:=calculate(result, variable, extern_variables)。
result:=calculate(arguments, extern_variables);
result:=combine(result, results);
//影響函數(shù)的外部環(huán)境，即修改外部變量
changeStatus(result, arguments, extern_variables);
return result;
}
籍比較兩段代碼，可以看出循環(huán)和遞歸具有相似的構(gòu)成，通過改變順序和適當(dāng)?shù)淖儞Q，任何循環(huán)都可以用遞歸的方式實現(xiàn)。程序簡單時，這種轉(zhuǎn)換很容易看出。比如下面這個簡單的累計求和函數(shù)：
//loop
function sum(num){
var result=1;
while (num>1){
result+=num;
num--;
}
return result;
}
對應(yīng)的遞歸形式:
//recursion
function sum2(num){
if (num>1){
return num+sum(num-1);
}else{
return 1;
}
}
反之，大部分遞歸程序也可以直接由循環(huán)來實現(xiàn)。下面是求最大公約數(shù)的循環(huán)形式的函數(shù)。
function gcd2(a, b){
var temp;
if (a<b){
temp=a;
a=b;
b=temp;
}
var c=a%b;
while (c!==0){
a=b;
b=c;
c=a%b;
}
return b;
}
不過，從遞歸到循環(huán)的轉(zhuǎn)換并不是都這么容易。遞歸偽代碼中的產(chǎn)生再次調(diào)用此函數(shù)的新參數(shù)部分
new_arguments:=conditional_get_next(arguments);
較之循環(huán)的對應(yīng)部分更為靈活?？梢园凑招庐a(chǎn)生的參數(shù)組數(shù)（函數(shù)需要的所有參數(shù)為一組）將遞歸分為兩類。第一類為參數(shù)組數(shù)固定，該遞歸可以轉(zhuǎn)換為循環(huán)，比如斐波那契數(shù)列和最大公約數(shù)的例子；第二類為參數(shù)組數(shù)不確定——就像在遍歷一個圖或樹的時候那樣，每個點有任意個相鄰的點——該遞歸不能直接轉(zhuǎn)換為循環(huán)。
因為循環(huán)只能做一維的重復(fù)，而遞歸可以遍歷二維的結(jié)構(gòu)。比如一棵樹中，一個節(jié)點既有它的子節(jié)點，也有同級的節(jié)點，簡單的一維循環(huán)不能夠在兩個方向上遍歷。
但是如果我們在循環(huán)中借助某種數(shù)據(jù)結(jié)構(gòu)記住有關(guān)節(jié)點位置的一些信息，第二類遞歸也可以用循環(huán)實現(xiàn)。
我們再通過一個例子來實踐上面觀察得出的結(jié)論。HTML5為Document和Element新定義了一個方法getElementsByClassName(names)，返回具有給定class值的所有elements。包括Firefox3在內(nèi)的一些瀏覽器已經(jīng)支持該方法。下面我們先用遞歸的方法給出一個功能較弱的版本，然后再用循環(huán)的方法重寫它。
var getElementsByClass={};
//elem為一個HTMLElement
//name為單個class名
//返回包含elem下所有class屬性包含給定名稱的element的數(shù)組
getElementsByClass.recursion1=function (elem, name){
var list=[];
function getElements(el){
if (el.className.split(' ').indexOf(name)>-1){
list.push(el);
}
for (var i=0, c=el.children; i<c.length; i++){
getElements(c[i]);
}
}
getElements(elem);
return list;
}
如前所述，在循環(huán)中為了記住節(jié)點的位置信息，我們需要一個能實現(xiàn)以下方法的數(shù)據(jù)結(jié)構(gòu)。
push(object) //寫入一個對象。
objectpop() //讀出最近寫入的一個對象，并將其從數(shù)據(jù)結(jié)構(gòu)中刪除。
objectget() //讀出最近寫入的一個對象，不改變數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。
堆棧正是這樣一個后進先出的數(shù)據(jù)結(jié)構(gòu)。Javascript中的Array對象支持前兩種方法，我們在為其增加第三個方法即可。
采用循環(huán)的版本：
getElementsByClass.loop1 = function(elem, name){
//use a js array as the basis of a needed stack
var stack = [];
stack.get = function(){
return stack[stack.length - 1];
}
var list = [];
//the business logic part. put the eligible element to the list.
function testElem(el){
if (el.className.split(' ').indexOf(name) > -1) {
list.push(el);
}
}
//check the root element
testElem(elem);
//initialize the stack
stack.push({
pointer: elem,
num: 0
});
var parent, num, el;
while (true) {
parent = stack.get();
el = parent.pointer.children[parent.num];
if (el) {//enter a deeper layer of the tree
testElem(el);
stack.push({
pointer: el,
num: 0
});
}
else {//return to the upper layer
if (stack.pop().pointer === elem) {
break;
}
else {
stack.get().num += 1;
}
}
}
return list;
}
歸納起來。所有循環(huán)都可以用遞歸實現(xiàn)；所有遞歸都可以用循環(huán)實現(xiàn)。采用哪種方法，由具體問題下哪種思路更方便直觀和使用者的喜好決定。
效率
性能方面，遞歸不比循環(huán)有優(yōu)勢。除了多次函數(shù)調(diào)用的開銷，在某些情況下，遞歸還會帶來不必要的重復(fù)計算。以計算斐波那契數(shù)列的遞歸程序為例。求第n項A(n)時，從第n-2項起，每一項都被重復(fù)計算。項數(shù)越小，重復(fù)的次數(shù)越多。令B(i)為第i項被計算的次數(shù)，則有
B(i)=1; i=n, n-1
B(i)=B(i+1)+B(i+2); i<n-1
這樣，B(i)形成了一個有趣的逆的斐波那契數(shù)列。求A(n)時有：
B(i)=A(n+1-i)
換一個角度來看，令C(i)為求A(i)時需要的加法的次數(shù)，則有
C(i)=0; i=0, 1
C(i)=1+C(i-1)+C(i-1); i>1
令D(i)=C(i)+1，有
D(i)=1; i=0, 1
D(i)=D(i-1)+D(i-1)
所以D(i)又形成一個斐波那契數(shù)列。并可因此得出：
C(n)=A(n+1)-1
而A(n)是以幾何級數(shù)增長，這種多余的重復(fù)在n較大時會變得十分驚人。與之相對應(yīng)的采用循環(huán)的程序，有
B(n)=1; n為任意值
C(n)=0; n=0, 1
C(n)=n-1; n>1
因而當(dāng)n較大時，前面給出的采用循環(huán)的程序會比采用遞歸的程序快很多。
如上一節(jié)中的循環(huán)一樣，遞歸中的這個缺陷也是可以彌補的。我們只需要記住已經(jīng)計算出來的項，求較高項時，就可以直接讀取以前的項。這種技術(shù)在遞歸中很普遍，被稱為“存儲”(memorization)。
下面是采用存儲技術(shù)的求斐波那契數(shù)列的遞歸算法。
//recursion with memorization
function fibonacci4(n){
var memory = []; //used to store each calculated item
function calc(n){
var result, p, q;
if (n < 2) {
memory[n] = n;
return n;
}
else {
p = memory[n - 1] ? memory[n - 1] : calc(n - 1);
q = memory[n - 2] ? memory[n - 2] : calc(n - 2);
result = p + q;
memory[n] = result;
return result;
}
}
return calc(n);
}
對于不同類型的需要重復(fù)計算的問題，循環(huán)和遞歸兩種方法各有所長，能給出更直觀簡單的方案。另一方面，循環(huán)和遞歸的方法可以互相轉(zhuǎn)換。任何一個循環(huán)的代碼都可以用遞歸改寫，實現(xiàn)相同的功能；反之亦然。在不失去其普遍性的前提下，可以把循環(huán)和遞歸分別用下列偽代碼概括。
偽代碼格式說明：循環(huán)采用while形式；變量不加定義；賦值用:=；條件表達式和執(zhí)行的語句都寫成函數(shù)的形式，圓括號內(nèi)寫上相關(guān)的值。其他語法方面，盡量接近Javascript的規(guī)范。
復(fù)制代碼 代碼如下:
//pseudo code of a loop
//while形式
function loop(arguments){
//結(jié)果的初始值
result:=initial_value;
while(condition(variable, arguments)){//循環(huán)條件，可能只需arguments，也可能為了方便引入循環(huán)變量
//計算結(jié)果。參數(shù)包括之前的結(jié)果、當(dāng)前循環(huán)變量和外部變量
result:=calculate(result, variable, extern_variables);
//影響函數(shù)的外部環(huán)境，即修改外部變量
changeStatus(result, variable, extern_variables);
//執(zhí)行完循環(huán)體中的語句后，修改參數(shù)或循環(huán)變量。
modify_arguments_variable(arguments, variable);
}
//返回結(jié)果
return result;
}
同樣我們給出遞歸函數(shù)的偽代碼。
復(fù)制代碼 代碼如下:
//pseudo code of a recursion
function recursion(arguments){
//以下代碼為控制函數(shù)重復(fù)調(diào)用的結(jié)構(gòu)部分。
//獲得再次調(diào)用此函數(shù)的新的參數(shù)，可能為多組arguments值。
//對應(yīng)于循環(huán)中的condition(variable, arguments)和modify_arguments_variable(arguments, variable)。
new_arguments:=conditional_get_next(arguments);
//對新參數(shù)的每一組，調(diào)用函數(shù)自身。
results:=recursion(new_arguments);
//以下的代碼為每次調(diào)用都運行的功能部分
//計算結(jié)果。涉及到之前的結(jié)果、當(dāng)前循環(huán)變量和外部變量。
//對應(yīng)于循環(huán)中的result:=calculate(result, variable, extern_variables)。
result:=calculate(arguments, extern_variables);
result:=combine(result, results);
//影響函數(shù)的外部環(huán)境，即修改外部變量
changeStatus(result, arguments, extern_variables);
return result;
}
籍比較兩段代碼，可以看出循環(huán)和遞歸具有相似的構(gòu)成，通過改變順序和適當(dāng)?shù)淖儞Q，任何循環(huán)都可以用遞歸的方式實現(xiàn)。程序簡單時，這種轉(zhuǎn)換很容易看出。比如下面這個簡單的累計求和函數(shù)：
復(fù)制代碼 代碼如下:
//loop
function sum(num){
var result=1;
while (num>1){
result+=num;
num--;
}
return result;
}
對應(yīng)的遞歸形式:
復(fù)制代碼 代碼如下:
//recursion
function sum2(num){
if (num>1){
return num+sum(num-1);
}else{
return 1;
}
}
反之，大部分遞歸程序也可以直接由循環(huán)來實現(xiàn)。下面是求最大公約數(shù)的循環(huán)形式的函數(shù)。
復(fù)制代碼 代碼如下:
function gcd2(a, b){
var temp;
if (a<b){
temp=a;
a=b;
b=temp;
}
var c=a%b;
while (c!==0){
a=b;
b=c;
c=a%b;
}
return b;
}
不過，從遞歸到循環(huán)的轉(zhuǎn)換并不是都這么容易。遞歸偽代碼中的產(chǎn)生再次調(diào)用此函數(shù)的新參數(shù)部分
new_arguments:=conditional_get_next(arguments);
較之循環(huán)的對應(yīng)部分更為靈活?？梢园凑招庐a(chǎn)生的參數(shù)組數(shù)（函數(shù)需要的所有參數(shù)為一組）將遞歸分為兩類。第一類為參數(shù)組數(shù)固定，該遞歸可以轉(zhuǎn)換為循環(huán)，比如斐波那契數(shù)列和最大公約數(shù)的例子；第二類為參數(shù)組數(shù)不確定——就像在遍歷一個圖或樹的時候那樣，每個點有任意個相鄰的點——該遞歸不能直接轉(zhuǎn)換為循環(huán)。
因為循環(huán)只能做一維的重復(fù)，而遞歸可以遍歷二維的結(jié)構(gòu)。比如一棵樹中，一個節(jié)點既有它的子節(jié)點，也有同級的節(jié)點，簡單的一維循環(huán)不能夠在兩個方向上遍歷。
但是如果我們在循環(huán)中借助某種數(shù)據(jù)結(jié)構(gòu)記住有關(guān)節(jié)點位置的一些信息，第二類遞歸也可以用循環(huán)實現(xiàn)。
我們再通過一個例子來實踐上面觀察得出的結(jié)論。HTML5為Document和Element新定義了一個方法getElementsByClassName(names)，返回具有給定class值的所有elements。包括Firefox3在內(nèi)的一些瀏覽器已經(jīng)支持該方法。下面我們先用遞歸的方法給出一個功能較弱的版本，然后再用循環(huán)的方法重寫它。
復(fù)制代碼 代碼如下:
var getElementsByClass={};
//elem為一個HTMLElement
//name為單個class名
//返回包含elem下所有class屬性包含給定名稱的element的數(shù)組
getElementsByClass.recursion1=function (elem, name){
var list=[];
function getElements(el){
if (el.className.split(' ').indexOf(name)>-1){
list.push(el);
}
for (var i=0, c=el.children; i<c.length; i++){
getElements(c[i]);
}
}
getElements(elem);
return list;
}
如前所述，在循環(huán)中為了記住節(jié)點的位置信息，我們需要一個能實現(xiàn)以下方法的數(shù)據(jù)結(jié)構(gòu)。
push(object) //寫入一個對象。
objectpop() //讀出最近寫入的一個對象，并將其從數(shù)據(jù)結(jié)構(gòu)中刪除。
objectget() //讀出最近寫入的一個對象，不改變數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。
堆棧正是這樣一個后進先出的數(shù)據(jù)結(jié)構(gòu)。Javascript中的Array對象支持前兩種方法，我們在為其增加第三個方法即可。
采用循環(huán)的版本：
復(fù)制代碼 代碼如下:
getElementsByClass.loop1 = function(elem, name){
//use a js array as the basis of a needed stack
var stack = [];
stack.get = function(){
return stack[stack.length - 1];
}
var list = [];
//the business logic part. put the eligible element to the list.
function testElem(el){
if (el.className.split(' ').indexOf(name) > -1) {
list.push(el);
}
}
//check the root element
testElem(elem);
//initialize the stack
stack.push({
pointer: elem,
num: 0
});
var parent, num, el;
while (true) {
parent = stack.get();
el = parent.pointer.children[parent.num];
if (el) {//enter a deeper layer of the tree
testElem(el);
stack.push({
pointer: el,
num: 0
});
}
else {//return to the upper layer
if (stack.pop().pointer === elem) {
break;
}
else {
stack.get().num += 1;
}
}
}
return list;
}
歸納起來。所有循環(huán)都可以用遞歸實現(xiàn)；所有遞歸都可以用循環(huán)實現(xiàn)。采用哪種方法，由具體問題下哪種思路更方便直觀和使用者的喜好決定。
效率
性能方面，遞歸不比循環(huán)有優(yōu)勢。除了多次函數(shù)調(diào)用的開銷，在某些情況下，遞歸還會帶來不必要的重復(fù)計算。以計算斐波那契數(shù)列的遞歸程序為例。求第n項A(n)時，從第n-2項起，每一項都被重復(fù)計算。項數(shù)越小，重復(fù)的次數(shù)越多。令B(i)為第i項被計算的次數(shù)，則有
B(i)=1; i=n, n-1
B(i)=B(i+1)+B(i+2); i<n-1
這樣，B(i)形成了一個有趣的逆的斐波那契數(shù)列。求A(n)時有：
B(i)=A(n+1-i)
換一個角度來看，令C(i)為求A(i)時需要的加法的次數(shù)，則有
C(i)=0; i=0, 1
C(i)=1+C(i-1)+C(i-1); i>1
令D(i)=C(i)+1，有
D(i)=1; i=0, 1
D(i)=D(i-1)+D(i-1)
所以D(i)又形成一個斐波那契數(shù)列。并可因此得出：
C(n)=A(n+1)-1
而A(n)是以幾何級數(shù)增長，這種多余的重復(fù)在n較大時會變得十分驚人。與之相對應(yīng)的采用循環(huán)的程序，有
B(n)=1; n為任意值
C(n)=0; n=0, 1
C(n)=n-1; n>1
因而當(dāng)n較大時，前面給出的采用循環(huán)的程序會比采用遞歸的程序快很多。
如上一節(jié)中的循環(huán)一樣，遞歸中的這個缺陷也是可以彌補的。我們只需要記住已經(jīng)計算出來的項，求較高項時，就可以直接讀取以前的項。這種技術(shù)在遞歸中很普遍，被稱為“存儲”(memorization)。
下面是采用存儲技術(shù)的求斐波那契數(shù)列的遞歸算法。
復(fù)制代碼 代碼如下:
//recursion with memorization
function fibonacci4(n){
var memory = []; //used to store each calculated item
function calc(n){
var result, p, q;
if (n < 2) {
memory[n] = n;
return n;
}
else {
p = memory[n - 1] ? memory[n - 1] : calc(n - 1);
q = memory[n - 2] ? memory[n - 2] : calc(n - 2);
result = p + q;
memory[n] = result;
return result;
}
}
return calc(n);
}
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于如何手動實現(xiàn)es5中的bind方法的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-12-12
使用鼠標(biāo)事件經(jīng)常碰到這樣的需求，比如獲取鼠標(biāo)相對于事件源的位置，鼠標(biāo)相對于事件源對象父元素的位置2011-09-09
這篇文章主要介紹了微信小程序圖表插件wx-charts用法,結(jié)合實例形式較為詳細的總結(jié)分析了微信小程序圖表插件wx-charts的功能、常見用法及相關(guān)操作注意事項,需要的朋友可以參考下2019-05-05
layui 根據(jù)后臺數(shù)據(jù)動態(tài)創(chuàng)建下拉框并同時默認選中的實例
今天小編就為大家分享一篇layui 根據(jù)后臺數(shù)據(jù)動態(tài)創(chuàng)建下拉框并同時默認選中的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-09-09
JavaScript監(jiān)測ActiveX控件是否已經(jīng)安裝過的代碼
這是通用的方法，只需要把唯一的Activex的clsid和任意一個屬性或方法名傳進來就可以判斷了。（找了兩個小時才找到 -_-!）2008-09-09
javascript面向?qū)ο笕筇卣髦鄳B(tài)實例詳解
這篇文章主要介紹了javascript面向?qū)ο笕筇卣髦鄳B(tài),結(jié)合實例形式詳細分析了javascript面向?qū)ο蟪绦蛟O(shè)計中多態(tài)的概念、原理,并結(jié)合實例形式總結(jié)了多態(tài)的實現(xiàn)方法與使用技巧,需要的朋友可以參考下2019-07-07
利用JavaScript做數(shù)獨的完整實現(xiàn)過程
數(shù)獨游戲是在一個9*9的方格中進行填數(shù)字的游戲,需要滿足的規(guī)則是每行每列和每個子九宮格都是1~9的不重復(fù)數(shù)字,下面這篇文章主要給大家介紹了關(guān)于如何利用JavaScript做數(shù)獨的相關(guān)資料,需要的朋友可以參考下
2021-09-09 
這篇文章主要介紹了微信小程序仿微信運動步數(shù)排行(交互)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2018-07-07 
JavaScript可以說是一個基于對象的編程語言，為什么說是基于對象而不是面向?qū)ο螅驗镴avaScript自身只實現(xiàn)了封裝，而沒有實現(xiàn)繼承和多態(tài)。
2009-07-07