遞歸函數

cgspine 發布于2019-08-23 12:28 / 413人閱讀

摘要：遞歸函數看過很多次但是感覺一直都沒有完全的理解這次有空看了下高級程序設計又靜下心來重新看了一遍遞歸感覺自己終于有一點明白了總結下自己解決這類問題的笨辦法哈哈遞歸函數是在一個函數通過名字調用自身的函數這個是書上的定義其實然并卵碰到類似的面試題

遞歸函數看過很多次,但是感覺一直都沒有完全的理解,這次有空看了下<>,又靜下心來重新看了一遍遞歸,感覺自己終于有一點明白了,總結下自己解決這類問題的笨辦法,哈哈

遞歸函數是在一個函數通過名字調用自身的函數
這個是書上的定義,其實然并卵,碰到類似的面試題一樣蒙蔽

先看一個書上的案例

function factorial(num){ 
    if (num <= 1){ 
         return 1; 
    } else { 
        return num * factorial(num-1); 
    } 
}

一個經典的階乘遞歸,看懂這段代碼很容易,但是讓你用遞歸寫個階乘,有些人就會悶逼了.
我的思路是

步驟1:找起點

    factorial(1) =  1  = 1   //要思考這個遞歸的起點在哪里,就像階乘就是1  而累加的話就是0
    factorial(2) =  2 * 1  =2  //接著我們試著多寫等式然后找出規律
    factorial(3) =  3 *  2  *  1 = 6
    factorial(4) =  4 *  3  *  2  * 1  = 24

步驟2:函數替換數字

    // 我們試著將等式右邊的實際變量用左邊的函數替換
    factorial(1) =  1  = 1
    factorial(2) =  2 * factorial(1) = 2    
    factorial(3) =  3 * factorial(2) = 6    
    factorial(4) =  4 * factorial(3) = 24

步驟3:找規律

    factorial(4) =  4 * factorial(3) = 24 
    //以的階乘為例  4! =  4 *  3!(3的階乘)
    //而3!其實就是這個函數本身,ta會繼續調用遞歸函數直至調用到factorial(1)
    
    //把4替換成參數
    factorial(n) =  n * factorial(n - 1)

步驟4:轉換成遞歸函數

    再看下步驟2
        情況1:起點
        factorial(1) =  1  = 1
        情況2:費起點
        factorial(2) =  2 * factorial(1) = 2    
        factorial(3) =  3 * factorial(2) = 6    
        factorial(4) =  4 * factorial(3) = 24  
     
    所以方法內應該需要兩種情況
        function  factorial(n){
            if(n>=1){
                 return  n *  factorial(n - 1)
            }else{
                return 1   //起點其實就是遞歸方法返回的起始值
            }
        }

如果還是沒有辦法理解這個遞歸函數,我們可以把所有遞歸拆成匿名函數

    //我們計算一個4階乘
    fun(4){
        return  4 *  fun(3)
    }
    
    fun(3){
        return 3 *  fun(2)
    }

    fun(2){
        return  2 *  fun(1)
    }
    
    fun(1){
        return 1 
    }

   你運行fun(4)的時候,一層一層想內訪問,訪問到fun(1)時候,再講所有的已知變量計算出結果
    fun(4)=>fun(3)=>fun(2)=>fun(1)=>fun(2)=>fun(3)=>fun(4)

    return  4 *  3 *  2 * 1

再用我的笨辦法試試其他例子,哈哈,應該能應付大部分的面試題了

栗子1:

    //計算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    //一個格子的時候只能走一步,所有只有一種走法
    // fn(2) =  2    //兩個格子的時候,可以一次走1個兩步,也可以走2個一步,所以是2種走法,后面就要拿個草稿紙算下了
    // fn(3) =  3    // fn(2) + fn(1)
    // fn(4) =  5    // fn(3) + fn(2)
    // fn(5) =  8    // fn(4) + fn(3)   //規律 :fn(n) =  fn(n-1) +  fn(n-2)  個人認為所有能做遞歸函數的,都是有規律可尋的.即便不是很理解其中的原理,但是通過代入數字,也是可以很快發現的這些相同之處,概括成函數的.
    
    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

我大概對遞歸函數的理解就這么多,如果有什么遞歸的面試題,可以留言一起探討下,哈哈

GPU云服務器云服務器遞歸函數printf 遞歸函數python js 異步函數遞歸樹形遞歸

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/98582.html

遞歸函數的執行

摘要：遞歸一個函數可以指向并調用自身。這是的一個獨特的用法，在這個結構下無法替代，出錯但我們可以用下面這種方式，把遞歸函數賦值給一個變量遞歸(Recursion) 一個函數可以指向并調用自身(call itself)。有三種方法可以達到這個目的：函數名 arguments.callee 作用域下的一個指向該函數的變量名上述概念引用自MDN，對遞歸概念不清楚的可以自行查看；遞歸函數...

tomato 2019-08-21 11:37 評論0 收藏0
翻譯連載 | 第 9 章：遞歸（下）－《JavaScript輕量級函數式編程》 |《你不知道的JS》

摘要：每個函數調用都將開辟出一小塊稱為堆棧幀的內存。當第二個函數開始執行，堆棧幀增加到個。當這個函數調用結束后，它的幀會從堆棧中退出。保持堆棧幀跟蹤函數調用的狀態，并將其分派給下一個遞歸調用迭。原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者關于譯者：這是一個流淌著滬江血液的純粹工程：認真，是 HTM...

LeviDing 2019-08-21 16:44 評論0 收藏0
ES6函數與Lambda演算

摘要：高階函數函數式編程中，接受函數作為參數，或者返回一個函數作為結果的函數通常就被稱為高階函數。均屬于高階函數，高階函數并不神秘，我們日常編程也會用到。參考演算函數式編程指南入門康托爾哥德爾圖靈永恒的金色對角線原文函數與演算緣起造了一個輪子，根據GitHub項目地址，生成項目目錄樹，直觀的展現項目結構，以便于介紹項目。歡迎Star。 repository-tree 技術棧： ES6 ...

fasss 2019-08-21 18:45 評論0 收藏0
【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現-鏈表與遞歸

摘要：鏈表與遞歸已經從底層完整實現了一個單鏈表這樣的數據結構，并且也依托鏈表這樣的數據結構實現了棧和隊列，在實現隊列的時候對鏈表進行了一些改進。計算這個區間內的所有數字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現，全部文...

lastSeries 2019-08-23 16:19 評論0 收藏0
【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現-鏈表與遞歸

摘要：鏈表與遞歸已經從底層完整實現了一個單鏈表這樣的數據結構，并且也依托鏈表這樣的數據結構實現了棧和隊列，在實現隊列的時候對鏈表進行了一些改進。計算這個區間內的所有數字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現，全部文...

alanoddsoff 2019-08-16 16:04 評論0 收藏0
翻譯連載 | 第 9 章：遞歸（上）－《JavaScript輕量級函數式編程》 |《你不知道的JS》

摘要：一旦我們滿足了基本條件值為，我們將不再調用遞歸函數，只是有效地執行了。遞歸深諳函數式編程之精髓，最被廣泛引證的原因是，在調用棧中，遞歸把大部分顯式狀態跟蹤換為了隱式狀態。原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者關于譯者：這是一個流淌著滬江血液的純粹工程：認真，是 HTML 最堅實的梁柱；...

MasonEast 2019-08-22 11:11 評論0 收藏0