快捷導(dǎo)航

循環(huán) vs 遞歸淺談

更新時間：2013年02月28日 17:45:48 作者：

本文代碼使用 JavaScript。一些同學(xué)對遞歸的理解還停留在“是一種求階乘比循環(huán)低效的方法”。但其實遞歸和循環(huán)處理的問題是不同。拿“遍歷數(shù)組”這個問題來說：循環(huán)適合同一維度（單層長度不限）上的遍歷，而遞歸則適合跨維度（層數(shù)不限）的遍歷。

比如遍歷以下一維數(shù)組：

復(fù)制代碼代碼如下:

[javascript] view plaincopyprint?
var a1 = [1];  
var a2 = [1, 2];  
var a3 = [1, 2, 3];  

雖然它們長度不一，但循環(huán)應(yīng)付它們非常容易，也很優(yōu)雅：

復(fù)制代碼代碼如下:

[javascript] view plaincopyprint?
var dumpArrayByLoop = function(a) {
    for (var i = 0; i < a.length; i++) {
        println(a[i]);
    }
};

如果改用遞歸，則看起來比較別扭：

復(fù)制代碼代碼如下:

[javascript] view plaincopyprint?
var dumpArrayByRecur = function(i, a) {
    if (i < a.length) {
        println(a[i]);
        dumpArrayByRecur(i + 1, a);
    }
};

它們能輸出同樣的結(jié)果，但相比之下遞歸版本看起來很笨拙。

現(xiàn)在想想，如果元數(shù)據(jù)變化了：維度擴(kuò)大到二維。

復(fù)制代碼代碼如下:

[javascript] view plaincopyprint?
var a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];

此時需要再外面再套一層循環(huán)變成雙重循環(huán)：

復(fù)制代碼代碼如下:

[javascript] view plaincopyprint?
var dumpArrayByLoop = function(a) {  
    for (var i = 0; i < a.length; i++) {  
        for (var j = 0; j < a[i].length; j++) {  
            println(a[i][j]);  
        }  
    }  
};  

如果數(shù)據(jù)的維度再繼續(xù)擴(kuò)大，變成三維、四維……甚至動態(tài)的N維數(shù)組。使用循環(huán)該怎么處理呢？

在這種“層數(shù)”很深，甚至不確定的情況下，就需要用“遞歸”來解決跨“層”的問題。

復(fù)制代碼代碼如下:

[javascript] view plaincopyprint?
var isArray = function(a) {
    return Object.prototype.toString.call(a) === '[object Array]';
};

var dumpArrayByRecur = function(a) {
    if (isArray(a)) {
        for (var i = 0; i < a.length; i++) {
            dumpArray(a[i]);
        }
    } else {
        println(a);
    }
};

上面的代碼中，如果發(fā)現(xiàn)子節(jié)點(diǎn)是一個數(shù)組，就使用遞歸進(jìn)入下一層；而同一層上的遍歷則使用循環(huán)來完成。