递归

递归

Posted by limantang on July 23, 2019

递归

  1. 在递归中, 每次的嵌套调用都会让函数体内部生成自己的局部变量

    正好可以用来保存不同状态下的数值, 省去了大量中间变量保存的工作

    极大的方便了设计和编程

  2. 递归就是将复杂的问题每次都解决一点点, 并将剩下的任务转化为更简单的问题

    等待下次求解, 如此反复,知道出现最简单情况(问题的出口)

  3. 递归和迭代都是基于循环实现的, 某些场合下他们是可以互相转化的

  4. 归并排序中的分治思想

    递归可以用来解决很多的排序问题, 其中两个算法归并排序和快速排序很好的体现了分治思想

    细说一下归并排序

    归并算法的核心就是归并, 就是把两个有序数列合并为更大的有序数列

    看个例子

    两个有序数组的合并过程

    [1, 2, 5, 8] [3, 4, 6]

            1      [1, 2, 5, 8]    
                   [3, 4, 6]
           
            2      [2, 5, 8]    
                   [3, 4, 6]
           
                   [5, 8]    
            3      [3, 4, 6]
           
                   [5, 8]    
            4      [4, 6]
           
            5      [5, 8]    
                   [6]
           
                   [8]    
            6      [6]
           
            8      [8]    
                   []
           
                   []    
                   []
           
        [1, 2, 3, 4, 5, 6, 8] 
    

    每次找出两个数组中最小的值然后放入新数组

    最终得到的新数组就是合并后的有序数组

  5. 归并排序中的问题简化

    上面说到的两个有序数列合并为更大的有序数列,很重要的前提是数列有序

    如果开始是两个乱序的数列呢, 如何合并为有序的数列呢

    其实可以利用递归的思想, 把问题不断简化, 把数列不断简化到只剩1个数

    1个数天然就是有序的

    最简单的思想是把长度n的数列每次简化为长度n - 1的数列直到长度为1

    但是这样没有并行性,效率很低

  6. 分而治之

    由于上面简化的步骤效率低

    所以就在归并排序中引入分而治之的方法

    就是将一个复杂问题, 分解成两个或者多个规模相同的子问题, 然后在对这些子问题继续细分, 直到子问题很简单, 很容易被求解出来, 那么这个复杂问题也就被求解出来了

  7. 归并排序中递归应用

利用0-9这10个数字的数组解释一下归并排序过程

  • 假设初始的数组为[7, 6, 2, 4, 1, 9, 3, 8, 0, 5],我们要对它进行从小到大的排序。

  • 第一次分解后,变成两个数组[7, 6, 2, 4, 1]和[9, 3, 8, 0, 5]。

  • 然后,我们将[7, 6, 2, 4, 1]分解为[7, 6]和[2, 4, 1],将[9, 3, 8, 0, 5]分解为[9, 3]和[8, 0, 5]。

  • 如果细分后的组仍然多于一个数字,我们就重复上述分解的步骤,直到每个组只包含一个数字。到这里,这些其实都是递归的嵌套调用过程。

  • 然后,我们要开始进行合并了。我们可以将{4, 1}分解为{4}和{1}。现在无法再细分了,我们开始合并。在合并的过程中进行排序,所以合并的结果为{1,4}。合并后的结果将返回当前函数的调用者,这就是函数返回的过程。

  • 重复上述合并的过程,直到完成整个数组的排序,得到[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。

    在上面的过程中注意三点

    • 数组分解(问题分治)
    • 数组合并(子问题合并)
    • 数组合并时的排序(求解子问题结果)

    归并排序使用分治思想, 而这个过程需要递归来实现

  1. 总结

    递归法和数学归纳法类似, 但是递归采用的事逆向递推, 化繁为简

    把复杂问题简化, 配合分治原理, 可以有效把问题细化,并行处理

    分治的思想包含了问题细分和结果合并

    正好对应递归编程中的函数嵌套调用和函数结果返回

    细分后的问题交给嵌套调用的函数去解决

    结果合并之后通过函数进行返回

    计算机中的函数嵌套调用正好对应了数学中的逆向递推

    弄懂了数学递推式,就能写出对应的递归代码

    由于递归编程在没有返回最终结果之前, 会保存大量中间变量

    所以比较消耗资源, 要注意递归深度(嵌套次数)