面對各種需要重複運算的問題,循環與遞迴這兩種思路各有所長,往往能給出更直觀簡潔的解法。另一方面,兩者是可以互相轉換的:任何一段循環邏輯都能改寫成遞迴,反之亦然。在不失普遍性的前提下,我們可以用下面的偽代碼分別概括這兩種結構。
偽代碼格式說明:循環採用 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);
比起循環的對應部分更為靈活。我們可以依「新產生的參數組數」把遞迴分成兩類:第一類是參數組數固定,這種遞迴可以轉換為循環,例如斐波那契數列與最大公因數;第二類是參數組數不確定,就像遍歷一個圖或樹時,每個節點可能有任意數量的相鄰節點,這種遞迴無法直接轉為循環。
原因在於,循環只能做一維的重複,而遞迴能遍歷二維結構。就拿樹來舉例,一個節點既有子節點,也有同層節點,單純的一維循環無法同時在兩個方向上遍歷。
但如果我們在循環中借助某種資料結構來記錄節點位置資訊,第二類遞迴同樣能用循環實作。
下面用一個實作來驗證上述結論。HTML5 為 Document 與 Element 新增了 getElementsByClassName(names) 方法,可回傳所有具有指定 class 值的元素。我們先用遞迴寫一個功能較弱的版本,再用循環改寫它。
程式碼如下:
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)=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);
}