JavaScript的遞迴與循環範例介紹_javascript技巧

遞歸與循環

對於不同類型的需要重複計算的問題，循環和遞歸兩種方法各有所長，能給出更直觀簡單的方案。另一方面，循環和遞歸的方法可以互相轉換。任何一個循環的程式碼都可以用遞歸改寫，實現相同的功能；反之亦然。在不失去其普遍性的前提下，可以把循環和遞歸分別用下列偽代碼概括。

偽代碼格式說明：循環採用while形式；變數不加定義；賦值用:=；條件表達式和執行的語句都寫成函數的形式，圓括號內寫上相關的值。其他語法方面，盡量接近Javascript的規格。

複製程式碼 代碼如下:

//pseudo code of a loop function loop(arguments){
//結果的初始值
result:=initial_value;

while(condition(variable, arguments)){//循環條件，可能只需arguments，也可能為了方便引入循環變數
//計算結果。參數包括先前的結果、目前循環變數和外部變數
result:=calculate(result, variable, extern_variables);
//影響函數的外部環境，即修改外部變數
changeStatus(result, variable , extern_variables);
//執行完循環體中的語句後，修改參數或循環變數。
modify_arguments_variable(arguments, variable);
}
//回傳結果
return result;
}

同樣我們給出遞歸函數的偽代碼。

複製代碼 代碼如下:

//pseudo code of recursion recursion = recursionfunction (arguments){
//以下程式碼為控制函數重複呼叫的結構部分。
//獲得再次呼叫此函數的新的參數，可能為多組arguments值。
//對應於循環中的condition(variable, arguments)和modify_arguments_variable(arguments, variable)。
new_arguments:=conditional_get_next(arguments);
//對新參數的每一組，呼叫函數本身。
results:=recursion(new_arguments);

//以下的程式碼為每次呼叫都執行的功能部分
//計算結果。涉及到先前的結果、當前循環變數和外部變數。
//對應於循環中的result:=calculate(result, variable, extern_variables)。
result:=calculate(arguments, extern_variables);
result:=combine(result, results);
//影響函數的外部環境，即修改外部變數
changeStatus(result, arguments, extern_variables);
return result;
}


籍比較兩段代碼，可以看出循環和遞歸具有相似的構成，透過改變順序和適當的變換，任何循環都可以用遞歸的方式實現。程序簡單時，這種轉換很容易看出。例如下面這個簡單的累計求和函數：

複製程式碼 程式碼如下:

/ loop

function sum(num){
var result=1;
while (num>1){
result =num;
num--;
}
return result;
}


對應的遞歸形式:

複製代碼 代碼如下:

//recursion

function sum2(num){
if (num>1){
return num sum(num-1);
}else {
return 1;
}
}


反之，大部分遞歸程式也可以直接由迴圈來實現。下面是求最大公約數的循環形式的函數。

複製程式碼 程式碼如下:

function gcd2(a, b){

var temp;
if (atemp=a;
a=b;
b=temp;
}
var c=a%b;
while (c!==0){
a=b;
b=c;
c=a%b;
}
return b;
}


不過，從遞歸到循環的轉換並不是都這麼容易。遞歸偽程式碼中的產生再次呼叫此函數的新參數部分

new_arguments:=conditional_get_next(arguments);

較之循環的對應部分更為靈活。可以依照新產生的參數組數（函數所需的所有參數為一組）將遞歸分為兩類。第一類為參數組數固定，此遞歸可以轉換為循環，例如斐波那契數列和最大公約數的例子；第二類為參數組數不確定——就像在遍歷一個圖或樹的時候那樣，每個點都有任意個相鄰的點－該遞迴不能直接轉換為迴圈。

因為循環只能做一維的重複，而遞歸可以遍歷二維的結構。例如一棵樹中，一個節點既有它的子節點，也有同級的節點，簡單的一維循環不能夠在兩個方向上遍歷。

但是如果我們在循環中藉助某種資料結構記住有關節點位置的一些信息，第二類遞歸也可以用循環實現。

我們再透過一個例子來實踐上面觀察得出的結論。 HTML5為Document和Element新定義了一個方法getElementsByClassName(names)，傳回具有給定class值的所有elements。包括Firefox3在內的一些瀏覽器已經支援此方法。下面我們先用遞歸的方法給一個功能較弱的版本，然後再用循環的方法重寫它。

複製程式碼 程式碼如下:

var getElementsByClass={}; //elem為一個HTMLElement
//name為單一class名稱
//傳回包含elem下所有class屬性包含給定名稱的element的陣列
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; igetElements(c[i]);
}
}
getElements(elem);
return list;
}


如前所述，在循環中為了記住節點的位置信息，我們需要一個能實現以下方法的資料結構。

push(object) //寫入一個物件。

objectpop() //讀出最近寫入的一個對象，並將其從資料結構中刪除。

objectget() //讀出最近寫入的一個對象，不改變資料結構的內容。

堆疊正是這樣一個後進先出的資料結構。 Javascript中的Array物件支援前兩種方法，我們在為其增加第三個方法即可。

採用循環的版本：

複製程式碼 程式碼如下: .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
});
}
num: 0
});
}
else {//return to the upper layer
if (stack.pop().pointer === elem) {
break;
}
else {
stack.get(). num = 1;
}
}
}

return list;
}

歸納起來。所有循環都可以用遞歸實現；所有遞歸都可以用循環實現。採用哪一種方法，由具體問題下哪一種思路較方便直覺和使用者的喜好決定。

效率

效能方面，遞歸不比循環有優勢。除了多次函數呼叫的開銷，在某些情況下，遞迴還會帶來不必要的重複計算。以計算斐波那契數列的遞歸程式為例。求第n項A(n)時，從第n-2項起，每一項都重複計算。項數越小，重複的次數越多。令B(i)為第i項被計算的次數，則有

B(i)=1; i=n, n-1

B(i)=B(i 1) B(i 2); i
這樣，B(i)形成了一個有趣的逆的斐波那契數列。求A(n)時有：

B(i)=A(n 1-i)

換一個角度來看，令C(i)為求A(i)時需要的加法的次數，則有

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)又形成一個斐波那契數列。並可因此得出：

C(n)=A(n 1)-1

而A(n)是以幾何級數增長，這種多餘的重複在n較大時會變得十分驚人。與之相對應的採用循環的程序，有

B(n)=1; n為任意值

C(n)=0; n=0, 1

C(n)=n-1; n>1

因而當n較大時，前面給出的採用循環的程序會比採用遞歸的程序快很多。

如上一節的循環一樣，遞歸中的這個缺陷也是可以彌補的。我們只需要記住已經計算出來的項，求較高項時，就可以直接讀取先前的項。這種技術在遞歸中很普遍，被稱為「儲存」(memorization)。

以下是採用儲存技術的求斐波那契數列的遞歸演算法。

複製程式碼 程式碼如下:

//recursion with memorization 4unction ){
var memory = []; //used to store each calculated item
function calc(n){
var result, p, q;
if (n 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);
}