資訊專欄INFORMATION COLUMN
摘要：遞歸函數(shù)看過很多次但是感覺一直都沒有完全的理解這次有空看了下高級(jí)程序設(shè)計(jì)又靜下心來重新看了一遍遞歸感覺自己終于有一點(diǎn)明白了總結(jié)下自己解決這類問題的笨辦法哈哈遞歸函數(shù)是在一個(gè)函數(shù)通過名字調(diào)用自身的函數(shù)這個(gè)是書上的定義其實(shí)然并卵碰到類似的面試題
遞歸函數(shù)看過很多次,但是感覺一直都沒有完全的理解,這次有空看了下<
遞歸函數(shù)是在一個(gè)函數(shù)通過名字調(diào)用自身的函數(shù)
這個(gè)是書上的定義,其實(shí)然并卵,碰到類似的面試題一樣蒙蔽
先看一個(gè)書上的案例
function factorial(num){
if (num <= 1){
return 1;
} else {
return num * factorial(num-1);
}
}
一個(gè)經(jīng)典的階乘遞歸,看懂這段代碼很容易,但是讓你用遞歸寫個(gè)階乘,有些人就會(huì)悶逼了.
我的思路是
步驟1:找起點(diǎn)
factorial(1) = 1 = 1 //要思考這個(gè)遞歸的起點(diǎn)在哪里,就像階乘就是1 而累加的話就是0
factorial(2) = 2 * 1 =2 //接著我們?cè)囍鄬懙仁饺缓笳页鲆?guī)律
factorial(3) = 3 * 2 * 1 = 6
factorial(4) = 4 * 3 * 2 * 1 = 24
步驟2:函數(shù)替換數(shù)字
// 我們?cè)囍鴮⒌仁接疫叺膶?shí)際變量用左邊的函數(shù)替換
factorial(1) = 1 = 1
factorial(2) = 2 * factorial(1) = 2
factorial(3) = 3 * factorial(2) = 6
factorial(4) = 4 * factorial(3) = 24
步驟3:找規(guī)律
factorial(4) = 4 * factorial(3) = 24
//以的階乘為例 4! = 4 * 3!(3的階乘)
//而3!其實(shí)就是這個(gè)函數(shù)本身,ta會(huì)繼續(xù)調(diào)用遞歸函數(shù)直至調(diào)用到factorial(1)
//把4替換成參數(shù)
factorial(n) = n * factorial(n - 1)
步驟4:轉(zhuǎn)換成遞歸函數(shù)
再看下步驟2
情況1:起點(diǎn)
factorial(1) = 1 = 1
情況2:費(fèi)起點(diǎn)
factorial(2) = 2 * factorial(1) = 2
factorial(3) = 3 * factorial(2) = 6
factorial(4) = 4 * factorial(3) = 24
所以方法內(nèi)應(yīng)該需要兩種情況
function factorial(n){
if(n>=1){
return n * factorial(n - 1)
}else{
return 1 //起點(diǎn)其實(shí)就是遞歸方法返回的起始值
}
}
如果還是沒有辦法理解這個(gè)遞歸函數(shù),我們可以把所有遞歸拆成匿名函數(shù)
//我們計(jì)算一個(gè)4階乘
fun(4){
return 4 * fun(3)
}
fun(3){
return 3 * fun(2)
}
fun(2){
return 2 * fun(1)
}
fun(1){
return 1
}
你運(yùn)行fun(4)的時(shí)候,一層一層想內(nèi)訪問,訪問到fun(1)時(shí)候,再講所有的已知變量計(jì)算出結(jié)果
fun(4)=>fun(3)=>fun(2)=>fun(1)=>fun(2)=>fun(3)=>fun(4)
return 4 * 3 * 2 * 1
再用我的笨辦法試試其他例子,哈哈,應(yīng)該能應(yīng)付大部分的面試題了
栗子1:
//計(jì)算1-10之間的和
//fun(0) = 0; //0
//fun(1) = 1; //1
//fun(2) = 2 + fun(1) //3
//fun(3) = 3 + fun(2) //6
//fun(4) = 4 + fun(3) //10
function fun(num){
if(num > 1){
return num + fun(num-1)
}else{
return 1
}
}
fun(10) //55
栗子2:
//一共有n格，每步可以走1格或者2格，問一共有多少走法。
// fn(1) = 1 //一個(gè)格子的時(shí)候只能走一步,所有只有一種走法
// fn(2) = 2 //兩個(gè)格子的時(shí)候,可以一次走1個(gè)兩步,也可以走2個(gè)一步,所以是2種走法,后面就要拿個(gè)草稿紙算下了
// fn(3) = 3 // fn(2) + fn(1)
// fn(4) = 5 // fn(3) + fn(2)
// fn(5) = 8 // fn(4) + fn(3) //規(guī)律 :fn(n) = fn(n-1) + fn(n-2) 個(gè)人認(rèn)為所有能做遞歸函數(shù)的,都是有規(guī)律可尋的.即便不是很理解其中的原理,但是通過代入數(shù)字,也是可以很快發(fā)現(xiàn)的這些相同之處,概括成函數(shù)的.
function fun(num){
if(num == 1){
return 1
}else if(num == 2){
return 2
}else{
return fun(num-1) + fun(num-2)
}
}
fun(5) // 8
我大概對(duì)遞歸函數(shù)的理解就這么多,如果有什么遞歸的面試題,可以留言一起探討下,哈哈
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/98582.html
摘要：遞歸一個(gè)函數(shù)可以指向并調(diào)用自身。這是的一個(gè)獨(dú)特的用法，在這個(gè)結(jié)構(gòu)下無法替代，出錯(cuò)但我們可以用下面這種方式，把遞歸函數(shù)賦值給一個(gè)變量 遞歸(Recursion) 一個(gè)函數(shù)可以指向并調(diào)用自身(call itself)。有三種方法可以達(dá)到這個(gè)目的： 函數(shù)名 arguments.callee 作用域下的一個(gè)指向該函數(shù)的變量名 上述概念引用自MDN，對(duì)遞歸概念不清楚的可以自行查看； 遞歸函數(shù)...
摘要：每個(gè)函數(shù)調(diào)用都將開辟出一小塊稱為堆棧幀的內(nèi)存。當(dāng)?shù)诙€(gè)函數(shù)開始執(zhí)行，堆棧幀增加到個(gè)。當(dāng)這個(gè)函數(shù)調(diào)用結(jié)束后，它的幀會(huì)從堆棧中退出。保持堆棧幀跟蹤函數(shù)調(diào)用的狀態(tài)，并將其分派給下一個(gè)遞歸調(diào)用迭。 原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者 關(guān)于譯者：這是一個(gè)流淌著滬江血液的純粹工程：認(rèn)真，是 HTM...
摘要：高階函數(shù)函數(shù)式編程中，接受函數(shù)作為參數(shù)，或者返回一個(gè)函數(shù)作為結(jié)果的函數(shù)通常就被稱為高階函數(shù)。均屬于高階函數(shù)，高階函數(shù)并不神秘，我們?nèi)粘＞幊桃矔?huì)用到。參考演算函數(shù)式編程指南入門康托爾哥德爾圖靈永恒的金色對(duì)角線原文函數(shù)與演算 緣起 造了一個(gè)輪子，根據(jù)GitHub項(xiàng)目地址，生成項(xiàng)目目錄樹，直觀的展現(xiàn)項(xiàng)目結(jié)構(gòu)，以便于介紹項(xiàng)目。歡迎Star。 repository-tree 技術(shù)棧： ES6 ...
摘要：鏈表與遞歸已經(jīng)從底層完整實(shí)現(xiàn)了一個(gè)單鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，并且也依托鏈表這樣的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了棧和隊(duì)列，在實(shí)現(xiàn)隊(duì)列的時(shí)候?qū)︽湵磉M(jìn)行了一些改進(jìn)。計(jì)算這個(gè)區(qū)間內(nèi)的所有數(shù)字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)，全部文...
摘要：鏈表與遞歸已經(jīng)從底層完整實(shí)現(xiàn)了一個(gè)單鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，并且也依托鏈表這樣的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了棧和隊(duì)列，在實(shí)現(xiàn)隊(duì)列的時(shí)候?qū)︽湵磉M(jìn)行了一些改進(jìn)。計(jì)算這個(gè)區(qū)間內(nèi)的所有數(shù)字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言 【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)，全部文...
摘要：一旦我們滿足了基本條件值為，我們將不再調(diào)用遞歸函數(shù)，只是有效地執(zhí)行了。遞歸深諳函數(shù)式編程之精髓，最被廣泛引證的原因是，在調(diào)用棧中，遞歸把大部分顯式狀態(tài)跟蹤換為了隱式狀態(tài)。 原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者 關(guān)于譯者：這是一個(gè)流淌著滬江血液的純粹工程：認(rèn)真，是 HTML 最堅(jiān)實(shí)的梁柱；...
閱讀 763·2021-11-23 09:51
閱讀 3354·2019-08-30 15:54
閱讀 489·2019-08-30 15:52
閱讀 3163·2019-08-30 13:58
閱讀 2989·2019-08-30 13:53
閱讀 2741·2019-08-29 14:18
閱讀 2484·2019-08-27 10:54
閱讀 2415·2019-08-26 18:09
