遞歸與循環
對于不同類型的需要重復計算的問題，循環和遞歸兩種方法各有所長，能給出更直觀簡單的方案。另一方面，循環和遞歸的方法可以互相轉換。任何一個循環的代碼都可以用遞歸改寫，實現相同的功能；反之亦然。在不失去其普遍性的前提下，可以把循環和遞歸分別用下列偽代碼概括。
偽代碼格式說明：循環采用while形式；變量不加定義；賦值用:=；條件表達式和執行的語句都寫成函數的形式，圓括號內寫上相關的值。其他語法方面，盡量接近Javascript的規范。
//pseudo code of a loop
//while形式
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 a recursion
function recursion(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 (a<b){
temp=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);
較之循環的對應部分更為靈活?？梢园凑招庐a生的參數組數（函數需要的所有參數為一組）將遞歸分為兩類。第一類為參數組數固定，該遞歸可以轉換為循環，比如斐波那契數列和最大公約數的例子；第二類為參數組數不確定――就像在遍歷一個圖或樹的時候那樣，每個點有任意個相鄰的點――該遞歸不能直接轉換為循環。
因為循環只能做一維的重復，而遞歸可以遍歷二維的結構。比如一棵樹中，一個節點既有它的子節點，也有同級的節點，簡單的一維循環不能夠在兩個方向上遍歷。
但是如果我們在循環中借助某種數據結構記住有關節點位置的一些信息，第二類遞歸也可以用循環實現。
我們再通過一個例子來實踐上面觀察得出的結論。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; i<c.length; i++){
getElements(c[i]);
}
}
getElements(elem);
return list;
}
如前所述，在循環中為了記住節點的位置信息，我們需要一個能實現以下方法的數據結構。
push(object) //寫入一個對象。
objectpop() //讀出最近寫入的一個對象，并將其從數據結構中刪除。
objectget() //讀出最近寫入的一個對象，不改變數據結構的內容。
堆棧正是這樣一個后進先出的數據結構。Javascript中的Array對象支持前兩種方法，我們在為其增加第三個方法即可。
采用循環的版本：
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;
}
歸納起來。所有循環都可以用遞歸實現；所有遞歸都可以用循環實現。采用哪種方法，由具體問題下哪種思路更方便直觀和使用者的喜好決定。
效率
性能方面，遞歸不比循環有優勢。除了多次函數調用的開銷，在某些情況下，遞歸還會帶來不必要的重復計算。以計算斐波那契數列的遞歸程序為例。求第n項A(n)時，從第n-2項起，每一項都被重復計算。項數越小，重復的次數越多。令B(i)為第i項被計算的次數，則有
B(i)=1; i=n, n-1
B(i)=B(i+1)+B(i+2); i<n-1
這樣，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
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);
}
