遞歸的概念

• 在程序中函數(shù)直接或間接調(diào)用自己
  1. 直接調(diào)用自己
  2. 間接調(diào)用自己
• 跳出結(jié)構(gòu),有了跳出才有結(jié)果

遞歸的思想

• 遞歸的調(diào)用,最終還是要轉(zhuǎn)換為自己這個函數(shù)
  1. 如果有個函數(shù)foo,如果他是遞歸函數(shù),到最后問題還是轉(zhuǎn)換為函數(shù)foo的形式
  2. 遞歸的思想就是將一個未知問題轉(zhuǎn)換為一個已解決的問題來實現(xiàn)

    function foo(){
        ...foo(...)...
    }

遞歸的步驟

1. 假設(shè)遞歸函數(shù)已經(jīng)寫好
2. 尋找遞推關(guān)系
3. 將遞推關(guān)系的結(jié)構(gòu)轉(zhuǎn)換為遞歸體
4. 將臨界條件加入到遞歸體中

經(jīng)典案例 1： 求和

求 1-100 的和

function sum(n) {
  if (n == 1) return 1
  return sum(n - 1) + n
}
復(fù)制代碼

經(jīng)典案例 2： 斐波拉契數(shù)列

1,1,2,3,5,8,13,21,34,55,89...求第 n 項

// 遞歸方法
function fib(n) {
  if (n === 1 || n === 2) return n - 1
  return fib(n - 1) + fib(n - 2)
}
console.log(fib(10)) // 34

//非遞歸方法 //
function fib(n) {
  let a = 0
  let b = 1
  let c = a + b
  for (let i = 3; i < n; i++) {
    a = b
    b = c
    c = a + b
  }
  return c
}
console.log(fib(10)) // 34
復(fù)制代碼

經(jīng)典案例 3： 爬樓梯

JS 遞歸 假如樓梯有 n 個臺階，每次可以走 1 個或 2 個臺階，請問走完這 n 個臺階有幾種走法

function climbStairs(n) {
  if (n == 1) return 1
  if (n == 2) return 2
  return climbStairs(n - 1) + climbStairs(n - 2)
}
復(fù)制代碼

經(jīng)典案例 4： 深拷貝

原理: clone(o) = new Object; 返回一個對象

function clone(o) {
  var temp = {}
  for (var key in o) {
    if (typeof o[key] == 'object') {
      temp[key] = clone(o[key])
    } else {
      temp[key] = o[key]
    }
  }
  return temp
}
復(fù)制代碼

經(jīng)典案例 5：vue中使用遞歸組件

• 遞歸組件: 組件在它的模板內(nèi)可以遞歸的調(diào)用自己，只要給組件設(shè)置 name 組件就可以了。
• 不過需要注意的是，必須給一個條件來限制數(shù)量，否則會拋出錯誤: max stack size exceeded
• 組件遞歸用來開發(fā)一些具體有未知層級關(guān)系的獨立組件。比如：聯(lián)級選擇器和樹形控件

<template>
  <div v-for="(item,index) in treeArr"> {{index}} <br/>
      <tree :item="item.arr" v-if="item.flag"></tree>
  </div>
</template>
<script>
export default {
  // 必須定義name，組件內(nèi)部才能遞歸調(diào)用
  name: 'tree',
  data(){
    return {}
  },
  // 接收外部傳入的值
  props: {
     item: {
      type:Array,
      default: ()=>[]
    }
  }
}
</script>

最后總結(jié)：

1、很多時候可以用遞歸代替循環(huán)，可以理解為遞歸是一種特殊的循環(huán)，但通常情況下不推薦這樣做。
2、遞歸一般是在函數(shù)里面把函數(shù)自己給調(diào)用一遍，通過每次調(diào)用改變條件，來結(jié)束循環(huán)。
3、遞歸在數(shù)據(jù)格式一致，在數(shù)據(jù)層級未知的情況下，比普通的遍歷更有優(yōu)勢。
4、遞歸在異步的時候，更容易理解，且更容易實現(xiàn)，因為可以在異步的回調(diào)里面，調(diào)用自己來實現(xiàn)每次都能拿到異步的結(jié)果再進行其他操作。
5、遞歸實現(xiàn)的快速排序比普通遍歷實現(xiàn)的排序效率更好。