javascript中遞歸指的是什么

這篇文章將為大家詳細(xì)講解有關(guān)javascript中遞歸指的是什么，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

1. 遞歸是啥?

遞歸概念很簡單，“自己調(diào)用自己”（下面以函數(shù)為例）。

在分析遞歸之前，需要了解下 JavaScript 中“壓?！保╟all stack） 概念。

2. 壓棧與出棧

棧是什么？可以理解是在內(nèi)存中某一塊區(qū)域，這個區(qū)域比喻成一個箱子，你往箱子里放些東西，這動作就是壓棧。所以最先放下去的東西在箱子最底下，最后放下去的在箱子最上面。把東西從箱子中拿出來可以理解為*出棧。

所以得出結(jié)論，我們有個習(xí)慣，拿東西是從上面往下拿，最先放下去的東西在箱子的最底下，最后才能拿到。

在 JavaScript 中，調(diào)用函數(shù)時，都會發(fā)生壓棧行為，遇到含 return 關(guān)鍵字的句子或執(zhí)行結(jié)束后，才會發(fā)生出棧（pop）。

來看個例子，這個段代碼執(zhí)行順序是怎樣的？

function fn1() {
    return 'this is fn1'
}

function fn2() {
    fn3()
    return 'this is fn2'
}

function fn3() {
    let arr = ['apple', 'banana', 'orange']
    return arr.length
}

function fn() {
    fn1()
    fn2()
    console.log('All fn are done')
}

fn()

上面發(fā)生了一系列壓棧出棧的行為：

1、首先，一開始棧（箱子）是空的

2、函數(shù) fn 執(zhí)行，fn 先壓棧，放在棧（箱子）最底下

3、在函數(shù) fn 內(nèi)部，先執(zhí)行函數(shù) fn1，fn1 壓棧在 fn 上面

4、函數(shù) fn1 執(zhí)行，遇到 return 關(guān)鍵字，返回 this is fn1，fn1 出棧，箱子里現(xiàn)在只剩下 fn

5、回到 fn 內(nèi)部，fn1 執(zhí)行完后，函數(shù) fn2 開始執(zhí)行，fn2 壓棧，但是在 fn2 內(nèi)部，遇到 fn3，開始執(zhí)行 fn3，所以 fn3 壓棧

6、此時棧中從下往上順序為：fn3 <= fn2 <= fn，fn 在最底下

7、以此類推，函數(shù) fn3 內(nèi)部遇到 return 關(guān)鍵字的句子，fn3 執(zhí)行完結(jié)束后出棧，回到函數(shù) fn2 中 ，fn2 也是遇到 return 關(guān)鍵字，繼續(xù)出棧。

8、現(xiàn)在棧中只有 fn 了，回到函數(shù) fn 中，執(zhí)行 console.log('All fn are done') 語句后，fn 出棧。

9、現(xiàn)在棧中又為空了。

上面步驟容易把人繞暈，下面是流程圖：

再看下在 chrome 瀏覽器環(huán)境下執(zhí)行：

3. 遞歸

先看下簡單的 JavaScript 遞歸

function sumRange(num) {
  if (num === 1) return 1;
  return num + sumRange(num - 1)
}

sumRange(3) // 6

上面代碼執(zhí)行順序：

1、函數(shù) sumRange(3) 執(zhí)行，sumRange(3) 壓棧，遇到 return 關(guān)鍵字，但這里還馬上不能出棧，因為調(diào)用了 sumRange(num - 1) 即 sumRange(2)

2、所以，sumRange(2) 壓棧,以此類推，sumRange(1) 壓棧，

3、最后，sumRange(1) 出棧返回 1，sumRange(2) 出棧，返回 2，sumRange(3) 出棧

4、所以 3 + 2 + 1 結(jié)果為 6

看流程圖

所以，遞歸也是個壓棧出棧的過程。

遞歸可以用非遞歸表示，下面是上面遞歸例子等價執(zhí)行

// for 循環(huán)
function multiple(num) {
    let total = 1;
    for (let i = num; i > 1; i--) {
        total *= i
    }
    return total
}
multiple(3)

4. 遞歸注意點

如果上面例子修改一下，如下：

function multiple(num) {
    if (num === 1) console.log(1)
    return num * multiple(num - 1)
}

multiple(3) // Error: Maximum call stack size exceeded

上面代碼第一行沒有 return 關(guān)鍵字句子，因為遞歸沒有終止條件，所以會一直壓棧，造成內(nèi)存泄漏。

遞歸容易出錯點

1. 沒有設(shè)置終止點

2. 除了遞歸，其他部分的代碼

3. 什么時候遞歸合適

好了，以上就是 JavaScript 方式遞歸的概念。

下面是練習(xí)題。

6. 練習(xí)題目

1、寫一個函數(shù)，接受一串字符串，返回一個字符串，這個字符串是將原來字符串倒過來。

2、寫一個函數(shù)，接受一串字符串，同時從前后開始拿一位字符對比，如果兩個相等，返回 true，如果不等，返回 false。

3、編寫一個函數(shù)，接受一個數(shù)組，返回扁平化新數(shù)組。

4、編寫一個函數(shù)，接受一個對象，這個對象值是偶數(shù)，則讓它們相加，返回這個總值。

5、編寫一個函數(shù)，接受一個對象，返回一個數(shù)組，這個數(shù)組包括對象里所有的值是字符串

7. 參考答案

參考1

function reverse(str) {
   if(str.length <= 1) return str; 
   return reverse(str.slice(1)) + str[0];
}
reverse('abc')

參考2

function isPalindrome(str){ 
    if(str.length === 1) return true;
    if(str.length === 2) return str[0] === str[1]; 
    if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1)) 
    return false; 
}
var str = 'abba'
isPalindrome(str)

參考3

function flatten (oldArr) {
   var newArr = [] 
   for(var i = 0; i < oldArr.length; i++){ 
    if(Array.isArray(oldArr[i])){ 
        newArr = newArr.concat(flatten(oldArr[i])) 
    } else { 
        newArr.push(oldArr[i])
     }
   }
   return newArr;
}
flatten([1,[2,[3,4]],5])

參考4

function nestedEvenSum(obj, sum=0) {
    for (var key in obj) { 
        if (typeof obj[key] === 'object'){ 
            sum += nestedEvenSum(obj[key]); 
        } else if (typeof obj[key] === 'number' && obj[key] % 2 === 0){ 
            sum += obj[key]; 
        }
     } 
     return sum;
}
nestedEvenSum({c: 4,d: {a: 2, b:3}})

參考5

function collectStrings(obj) {
    let newArr = []
    for (let key in obj) {
        if (typeof obj[key] === 'string') {
            newArr.push(obj[key])
        } else if(typeof obj[key] === 'object' && !Array.isArray(obj[key])) {
           newArr = newArr.concat(collectStrings(obj[key]))
        }
    }
    return newArr
}
var obj = {
        a: '1',
        b: {
            c: 2,
            d: 'dd'
        }
    }
collectStrings(obj)

關(guān)于“javascript中遞歸指的是什么”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。