递归函数

cgspine 发布于2019-08-23 12:28 / 301人阅读

摘要：递归函数看过很多次但是感觉一直都没有完全的理解这次有空看了下高级程序设计又静下心来重新看了一遍递归感觉自己终于有一点明白了总结下自己解决这类问题的笨办法哈哈递归函数是在一个函数通过名字调用自身的函数这个是书上的定义其实然并卵碰到类似的面试题

递归函数看过很多次,但是感觉一直都没有完全的理解,这次有空看了下<>,又静下心来重新看了一遍递归,感觉自己终于有一点明白了,总结下自己解决这类问题的笨办法,哈哈

递归函数是在一个函数通过名字调用自身的函数
这个是书上的定义,其实然并卵,碰到类似的面试题一样蒙蔽

先看一个书上的案例

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 异步函数递归树形递归

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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