什么是遞歸，它是如何工作的？

我們先來看一下遞歸（recursion）的定義：

遞歸是一種解決問題的有效方法，在遞歸過程中，函數(shù)將自身作為子例程調(diào)用。

簡單說程序調(diào)用自身的編程技巧叫遞歸。遞歸的思想是把一個(gè)大型復(fù)雜問題層層轉(zhuǎn)化為一個(gè)與原問題規(guī)模更小的問題，問題被拆解成子問題后，遞歸調(diào)用繼續(xù)進(jìn)行，直到子問題無需進(jìn)一步遞歸就可以解決的地步為止。

使用遞歸需要避免出現(xiàn)死循環(huán)，為了確保遞歸正確工作，遞歸程序應(yīng)該包含2個(gè)屬性：

1. 基本情況（bottom cases），基本情況用于保證程序調(diào)用及時(shí)返回，不在繼續(xù)遞歸，保證了程序可終止。
2. 遞推關(guān)系（recurrentce relation），可將所有其他情況拆分到基本案例。

函數(shù)中自己調(diào)用自己就是遞歸，切記要有終止條件，不然進(jìn)入死循環(huán)     

一、求和

（1）數(shù)字求和

    function sum(n){
      if(n===1){
        return n=1
      }
      return n+sum(n-1)
    }
    console.log(sum(5));

 執(zhí)行順序

5+sum(n-1)
5+4+sum(n-1)
5+4+3+sum(n-1)
5+4+3+2sum(n-1)
5+4+3+2+1

（2）數(shù)組求和

        function sum(arr) {
        var len = arr.length
        if (len == 0) {
          return 0
        } else if (len == 1) {
          return arr[0]
        } else {
          return arr[0] + sum(arr.slice(1))
        }
      }
      let arr = [ 1, 2, 3, 4, 5 ]  
      console.log(sum(arr))

執(zhí)行順序

1+sum(2,3,4,5)
1+2+sum(3,4,5)
1+2+3(4,5)
1+2+3+4+sum(5)
1+2+3+4+5
1+2+3+9
1+2+12
1+14
15

二、數(shù)據(jù)轉(zhuǎn)樹

        let data = [{
                id: "01",
                pid: "",
                "name": "老王"
            },
            {
                id: "02",
                pid: "01",
                "name": "小張"
            }
        ]

  function fn(data, rootId = '') {
            const children = []      //定義一個(gè)空數(shù)組
            data.forEach(item => {
                if (item.pid === rootId) {    //如果每一項(xiàng)的pid=rootId就添加到數(shù)組里
                    children.push(item)
                    item.children = fn(data, item.id)
                }
            });
            return children
        }

使用遞歸轉(zhuǎn)樹 要知道根的pid是什么值才能進(jìn)行下一步操作，作為起點(diǎn)。

執(zhí)行順序

三、漢諾塔

規(guī)則 下面三個(gè)柱子分別設(shè)為 a 、b、 c、 目標(biāo)把a(bǔ)中的所有盤子分別從大到小依次放到c柱子中，每次只能移動一個(gè)盤子

實(shí)現(xiàn)思路：

1. 將n-1個(gè)盤子從a挪到b
2. 將n盤子從a挪到c
3. 將n-1個(gè)盤子從b挪到c

        function fn(num, start, middle, end) {   
            if(num>0){
                fn(num-1,start,end,middle)
                console.log(start+'====>'+end); 
                fn(num-1,middle,start,end)
            }
           }
              fn(2,'a','b','c')

把  num作為盤子的數(shù)量  start 作為a盤子  middle作為b盤子   end作為c盤子  

例如 2個(gè)盤子的執(zhí)行順序

1.第一行 把2帶進(jìn)去 num>0  執(zhí)行第一個(gè)函數(shù)fn(2-1,start,end,middle) 又去執(zhí)行了fn(1-1,start,end,middle) 發(fā)現(xiàn)num不大于0不僅如此if條件，回過來看 fn(2-1,start,end,middle) ,輸出 console.log(a===>b) 

2.第二行console.log(start+'====>'+end);   直接輸出 a===>c

3.第三行 fn(2-1,middle,start,end)  執(zhí)行 console.log(b===>c)  下次再去執(zhí)行  fn(1-1,middle,start,end) 進(jìn)入不了循環(huán)執(zhí)行完畢

執(zhí)行順序有點(diǎn)抽象，實(shí)在不理解就按照最簡單的思路去做 fn(num, start, middle, end) ，平常我們玩游戲怎么玩就去怎么做，初始圖

fn(num-1,start,middle,end)  把 第二個(gè)的參數(shù)位置作為要移動的盤子 把第四個(gè)的參數(shù)位置作為移動目標(biāo)    每次看圖把這個(gè)公式帶進(jìn)去 

第一步   fn(num-1,start,end,middle)   例如兩個(gè)盤子 肯定是先把a(bǔ)-1放到b上  

第二步 把盤子a放c上直接輸出 console.log('a===>c')

第三步 把盤子b放c上  fn(num-1,middle,start,end,) 

四、斐波那契數(shù)列

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、

        function Fibonacci(n) {
            return  n <= 1?1:Fibonacci(n - 1) + Fibonacci(n - 2)
        }

除了前兩個(gè) 每次都是前一個(gè)數(shù)和前兩個(gè)數(shù)的和相加等于第三個(gè)數(shù) 

例如數(shù)字5舉例  前一項(xiàng)是3  前兩項(xiàng)是2    3+2=5   

總結(jié)

到此這篇關(guān)于JavaScript遞歸經(jīng)典案例題詳析的文章就介紹到這了,更多相關(guān)JavaScript遞歸案例內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論