關(guān)于JavaScript遞歸經(jīng)典案例題詳析
什么是遞歸,它是如何工作的?
我們先來看一下遞歸(recursion)的定義:
遞歸是一種解決問題的有效方法,在遞歸過程中,函數(shù)將自身作為子例程調(diào)用。
簡單說程序調(diào)用自身的編程技巧叫遞歸。遞歸的思想是把一個大型復(fù)雜問題層層轉(zhuǎn)化為一個與原問題規(guī)模更小的問題,問題被拆解成子問題后,遞歸調(diào)用繼續(xù)進(jìn)行,直到子問題無需進(jìn)一步遞歸就可以解決的地步為止。
使用遞歸需要避免出現(xiàn)死循環(huán),為了確保遞歸正確工作,遞歸程序應(yīng)該包含2個屬性:
- 基本情況(bottom cases),基本情況用于保證程序調(diào)用及時返回,不在繼續(xù)遞歸,保證了程序可終止。
- 遞推關(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 = [] //定義一個空數(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ī)則 下面三個柱子分別設(shè)為 a 、b、 c、 目標(biāo)把a(bǔ)中的所有盤子分別從大到小依次放到c柱子中,每次只能移動一個盤子
實(shí)現(xiàn)思路:
- 將n-1個盤子從a挪到b
- 將n盤子從a挪到c
- 將n-1個盤子從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個盤子的執(zhí)行順序
1.第一行 把2帶進(jìn)去 num>0 執(zhí)行第一個函數(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) 把 第二個的參數(shù)位置作為要移動的盤子 把第四個的參數(shù)位置作為移動目標(biāo) 每次看圖把這個公式帶進(jìn)去
第一步 fn(num-1,start,end,middle) 例如兩個盤子 肯定是先把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ù)列”,指的是這樣一個數(shù)列:0、1、1、2、3、5、8、13、21、34、
function Fibonacci(n) { return n <= 1?1:Fibonacci(n - 1) + Fibonacci(n - 2) }
除了前兩個 每次都是前一個數(shù)和前兩個數(shù)的和相加等于第三個數(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)文章希望大家以后多多支持腳本之家!
相關(guān)文章
微信小程序使用canvas畫圖保存圖片到手機(jī)相冊代碼示例
在微信小程序中利用canvas?API繪制圖形后,可通過CanvasContext.draw方法將圖形渲染到畫布,并使用wx.canvasToTempFilePath將畫布導(dǎo)出為圖片,再通過wx.saveImageToPhotosAlbum方法保存到手機(jī)相冊,,需要的朋友可以參考下2024-09-09鼠標(biāo)移動到圖片名上,顯示圖片的簡單實(shí)例
鼠標(biāo)移動到名(wait.gif)上,顯示圖片,鼠標(biāo)移開則不顯示圖片2013-07-07JavaScript讀寫二進(jìn)制數(shù)據(jù)的方法詳解
avascript里有兩個內(nèi)置對象,一個是ArrayBuffer;一個是DataView,讀寫二進(jìn)制數(shù)據(jù)都需要使用這兩個對象。這篇文章主要給大家介紹了關(guān)于JavaScript讀寫二進(jìn)制數(shù)據(jù)的方法,需要的朋友可以參考下2018-09-09ECMAScript?數(shù)據(jù)類型之Number類型
這篇文章主要介紹了?ECMAScript?數(shù)據(jù)類型之Number類型,Number類型使用IEEE?754格式表示整數(shù)和浮點(diǎn)值,更多相關(guān)內(nèi)容請需要的小伙伴參考下面文章內(nèi)容2022-06-06