遞歸是什么？
想個標(biāo)題已經(jīng)讓我很糾結(jié)了，究竟是函數(shù)遞歸還是遞歸函數(shù)？
看了下MDN的說明是：** 函數(shù)可以被遞歸，就是說函數(shù)可以調(diào)用其本身。**
那遞歸就是函數(shù)的里面再調(diào)用自己，從而形成一個循環(huán)。
還是在實戰(zhàn)才會學(xué)得更快，來戰(zhàn)吧。
用遞歸計算階乘:
function factorial(n){
return (n * factorial(n - 1));
}
這里就是函數(shù)里，調(diào)用了自己不停的互乘。當(dāng)運行factorial(5)就不停計算 5*4*3*2...的計算下去，但問題是這沒有盡頭呀！直到棧溢出拋出 Uncaught RangeError: Maximum call stack size exceeded(…) 也不會有返回值。
這種無盡的遞歸稱為死遞歸，它和死循環(huán)一樣恐怖。
所有循環(huán)的程序都會有一個退出條件，對于每一個遞歸的程序，也都會有一個退出條件，加入退出條件后，函數(shù)就成了這樣：
function factorial(n){
if ((n == 0) || (n == 1))
return 1;
else
return (n * factorial(n - 1));
}
factorial(5); // 120
使用遞歸的時候要注意出口,不return出口會造成死循環(huán)。
看到這里，你可能會想說遞歸不就是循環(huán)嗎？這種for都可以簡單實現(xiàn)啦。
沒錯，遞歸就是一個循環(huán)，自身的一個循環(huán)。
循環(huán)的時間復(fù)雜度和空間復(fù)雜度都優(yōu)于用遞歸實現(xiàn)。
遞歸是方法調(diào)用本身,總是要進出堆棧內(nèi)存,容易導(dǎo)致內(nèi)存溢出,并且運行慢,循環(huán)是直接在內(nèi)存中執(zhí)行,速度快。
遞歸的優(yōu)越性在于條理清晰，可讀性強，比較適宜于問題本身是遞歸性質(zhì)的、用循環(huán)難于解決的問題。在二者都不難的情況下，一般都是優(yōu)先選用循環(huán)來解決問題的。
寫一個99乘法表
這一個簡單的實戰(zhàn)例子，相信剛開始學(xué)javascript時，老師都給你布置這道作業(yè)，直接用兩個for就可以輕松實現(xiàn):
可以直接復(fù)雜代碼，放到控制臺就可以運行
for(var i=1; i<=9; i++){
for(var j=1; j<=i; j++){
document.writeln(j+" x "+i+"="+i*j);
if (j==i) {
document.writeln("<br>");
}
}
}
效果如下：
讓我跟據(jù)遞歸簡單的實現(xiàn)一個：
var ss = function(x){
if(x>0 && x<=9){
for(var i=1;i<=x;i++){
document.writeln(i+"x"+x+"="+x*i);
if(i==x){
document.write("<br>");
}
}
ss(++x)
}
}
ss(1)//從1開始;改成9，函數(shù)里就要改成減了，實現(xiàn)出來就倒過來了
效果一模一樣(哈哈，其實我是用了同一張圖...)：
上面函數(shù)還是有用到for呀，下面我們用純的：
var jj = function(x,y){
if(x==1&&y==1){
document.writeln(x+"x"+y+"="+x*y);
return false;//注意這個return出口，不然會死循環(huán)
}
if(y==1){
document.writeln(x+"x"+y+"="+x*y);
document.writeln("<br>");
x--;
y=x;
}else{
document.writeln(x+"x"+y+"="+x*y);
--y;
}
jj(x,y);
}
jj(9,9)
這個也可以實現(xiàn)效果，只是真的是倒過來了(哈哈....)
** 在知乎看到有個大神，用遞歸實現(xiàn) javascript 中常用的 forEach map filter 函數(shù)。
作者：韋捷 訪問地址：https://www.zhihu.com/question/54359554/answer/139040476 **
下面讓我把實現(xiàn)方法搬運過來裝裝逼：
先編寫兩個輔助函數(shù)：
// 得到 array 的第一個元素
// head([1,2,3,4,5])
// => 1
var head = function (array) {
return array[0]
}
// 得到 array 除第一個元素外的其他元素
// tail([1,2,3,4,5])
// => [2,3,4,5]
var tail = function (array) {
return array.slice(1, array.length)
}
forEach 時會遍歷作為第一個參數(shù)的數(shù)組，并且逐個將數(shù)組中的成員作為參數(shù)傳給 fn 函數(shù)執(zhí)行。
var forEach = function (array, fn) {
if (array.length > 0) {
fn(head(array))//傳進的函數(shù)調(diào)用數(shù)組的第一個值
forEach(tail(array), fn)//重新調(diào)用剩下的數(shù)組
}
}
forEach([1,2,3], function (x) { console.log(x) })
// => 1
// => 2
// => 3
map 時會遍歷作為第一個參數(shù)的數(shù)組，并且逐個將數(shù)組中的成員作為參數(shù)傳給 fn 函數(shù)執(zhí)行，然后將 fn 的返回值逐個裝入新數(shù)組，最后返回新數(shù)組。
var map = function (array, fn) {
if (array.length > 0) {
return [fn(head(array))].concat(map(tail(array), fn))//實現(xiàn)每個值+1后合并
} else {
return []
}
}
map([1,2,3], function (x) { return x+1 })
// => [2,3,4]
filter 時會遍歷作為第一個參數(shù)的數(shù)組，并且逐個將數(shù)組中的成員作為參數(shù)傳給 fn 函數(shù)執(zhí)行，如果 fn 的返回值是 true 則將當(dāng)前參數(shù)裝入新數(shù)組，否則忽略當(dāng)前參數(shù)，最后返回新數(shù)組。
var filter = function (array, fn) {
if (array.length > 0) {
if (fn(head(array)) === true) {
return [head(array)].concat(filter(tail(array), fn))//實現(xiàn)每個>2的值合并
} else {
return [].concat(filter(tail(array), fn))
}
} else {
return []
}
}
filter([1,2,3,4,5], function (x) { return x>2 })
// => [3,4,5]
JSON中最常用到
用到了遞歸函數(shù)，用來調(diào)用json的子節(jié)點，把所有json中的子節(jié)點中包含某個數(shù)的object，都push到一個數(shù)組中，然后對其進行綁定。
var arr=[];
function getData(data){
if(data.itemId=="4323"){
arr.push(item_data);
}
if(data.Childs){
if(data.Childs.length>0){
getChilds(data.Childs)
}
}
}
function getChilds(data){
for(var i=0;i<data.length;i++){
getData(data[i]);
}
}
更深入的應(yīng)用還有二叉樹的遍歷等...
** 參考資料 **
