递归 订阅
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。 展开全文
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
信息
外文名
recursion
分    类
计算机算法
中文名
递归
属    性
编程技巧
递归递归定义
递归,就是在运行的过程中调用自己。构成递归需具备的条件: 1. 子问题须与原始问题为同样的事,且更为简单;2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。在数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。例如,下列为某人祖先的递归定义:某人的双亲是他的祖先(基本情况)。某人祖先的双亲同样是某人的祖先(递归步骤)。斐波纳契数列(Fibonacci Sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21..... I [1]  斐波纳契数列是典型的递归案例:递归关系就是实体自己和自己建立关系。Fib(0) = 1 [基本情况] Fib(1) = 1 [基本情况] 对所有n > 1的整数:Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示,但在实际应用中,递归定义的高开销往往会让人望而却步。例如:阶乘(1) = 1 [基本情况] 对所有n > 1的整数:阶乘(n) = (n * 阶乘(n-1)) [递归定义] 一种便于理解的心理模型,是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如:你怎样才能移动100个箱子?答案:你首先移动一个箱子,并记下它移动到的位置,然后再去解决较小的问题:你怎样才能移动99个箱子?最终,你的问题将变为怎样移动一个箱子,而这时你已经知道该怎么做的。如此的定义在数学中十分常见。例如,集合论对自然数的正式定义是:1是一个自然数,每个自然数都有一个后继,这一个后继也是自然数。 德罗斯特效应是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片,进而小图片中还有更小的一幅她手持同一物体的图片,依此类推。又例如,我们在两面相对的镜子之间放一根正在燃烧的蜡烛,我们会从其中一面镜子里看到一根蜡烛,蜡烛后面又有一面镜子,镜子里面又有一根蜡烛……这也是递归的表现。
收起全文
精华内容
下载资源
问答
  • 为什么你学不会递归?告别递归,谈谈我的经验

    万次阅读 多人点赞 2019-10-27 16:01:40
    可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了! 可能也有一大部分人知道递归,也能看的懂递归,但在...

    可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了!

    可能也有一大部分人知道递归,也能看的懂递归,但在实际做题过程中,却不知道怎么使用,有时候还容易被递归给搞晕。也有好几个人来问我有没有快速掌握递归的捷径啊。说实话,哪来那么多捷径啊,不过,我还是想写一篇文章,谈谈我的一些经验,或许,能够给你带来一些帮助。

    为了兼顾初学者,我会从最简单的题讲起!

    递归的三大要素

    第一要素:明确你这个函数想要干什么

    对于递归,我觉得很重要的一个事就是,这个函数的功能是什么,他要完成什么样的一件事,而这个,是完全由你自己来定义的。也就是说,我们先不管函数里面的代码什么,而是要先明白,你这个函数是要用来干什么。

    例如,我定义了一个函数

    // 算 n 的阶乘(假设n不为0)
    int f(int n){
        
    }
    

    这个函数的功能是算 n 的阶乘。好了,我们已经定义了一个函数,并且定义了它的功能是什么,接下来我们看第二要素。

    第二要素:寻找递归结束条件

    所谓递归,就是会在函数内部代码中,调用这个函数本身,所以,我们必须要找出递归的结束条件,不然的话,会一直调用自己,进入无底洞。也就是说,我们需要找出当参数为啥时,递归结束,之后直接把结果返回,请注意,这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。

    例如,上面那个例子,当 n = 1 时,那你应该能够直接知道 f(n) 是啥吧?此时,f(1) = 1。完善我们函数内部的代码,把第二要素加进代码里面,如下

    // 算 n 的阶乘(假设n不为0)
    int f(int n){
        if(n == 1){
            return 1;
        }
    }
    

    有人可能会说,当 n = 2 时,那我们可以直接知道 f(n) 等于多少啊,那我可以把 n = 2 作为递归的结束条件吗?

    当然可以,只要你觉得参数是什么时,你能够直接知道函数的结果,那么你就可以把这个参数作为结束的条件,所以下面这段代码也是可以的。

    // 算 n 的阶乘(假设n>=2)
    int f(int n){
        if(n == 2){
            return 2;
        }
    }
    

    注意我代码里面写的注释,假设 n >= 2,因为如果 n = 1时,会被漏掉,当 n <= 2时,f(n) = n,所以为了更加严谨,我们可以写成这样:

    // 算 n 的阶乘(假设n不为0)
    int f(int n){
        if(n <= 2){
            return n;
        }
    }
    

    第三要素:找出函数的等价关系式

    第三要素就是,我们要不断缩小参数的范围,缩小之后,我们可以通过一些辅助的变量或者操作,使原函数的结果不变。

    例如,f(n) 这个范围比较大,我们可以让 f(n) = n * f(n-1)。这样,范围就由 n 变成了 n-1 了,范围变小了,并且为了原函数f(n) 不变,我们需要让 f(n-1) 乘以 n。

    说白了,就是要找到原函数的一个等价关系式,f(n) 的等价关系式为 n * f(n-1),即

    f(n) = n * f(n-1)。

    这个等价关系式的寻找,可以说是最难的一步了,如果你不大懂也没关系,因为你不是天才,你还需要多接触几道题,我会在接下来的文章中,找 10 道递归题,让你慢慢熟悉起来

    找出了这个等价,继续完善我们的代码,我们把这个等价式写进函数里。如下:

    // 算 n 的阶乘(假设n不为0)
    int f(int n){
        if(n <= 2){
            return n;
        }
        // 把 f(n) 的等价操作写进去
        return f(n-1) * n;
    }
    

    至此,递归三要素已经都写进代码里了,所以这个 f(n) 功能的内部代码我们已经写好了。

    这就是递归最重要的三要素,每次做递归的时候,你就强迫自己试着去寻找这三个要素。

    还是不懂?没关系,我再按照这个模式讲一些题。

    有些有点小基础的可能觉得我写的太简单了,没耐心看?少侠,请继续看,我下面还会讲如何优化递归。当然,大佬请随意,可以直接拉动最下面留言给我一些建议,万分感谢!

    案例1:斐波那契数列

    斐波那契数列的是这样一个数列:1、1、2、3、5、8、13、21、34…,即第一项 f(1) = 1,第二项 f(2) = 1…,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

    1、第一递归函数功能

    假设 f(n) 的功能是求第 n 项的值,代码如下:

    int f(int n){
        
    }
    

    2、找出递归结束的条件

    显然,当 n = 1 或者 n = 2 ,我们可以轻易着知道结果 f(1) = f(2) = 1。所以递归结束条件可以为 n <= 2 时,f(n= = 1。代码如下:

    int f(int n){
        if(n <= 2){
            return 1;
        }
    }
    

    第三要素:找出函数的等价关系式

    题目已经把等价关系式给我们了,所以我们很容易就能够知道 f(n) = f(n-1) + f(n-2)。我说过,等价关系式是最难找的一个,而这个题目却把关系式给我们了,这也太容易,好吧,我这是为了兼顾几乎零基础的读者。

    所以最终代码如下:

    int f(int n){
        // 1.先写递归结束条件
        if(n <= 2){
            return 1;
        }
        // 2.接着写等价关系式
        return f(n-1) + f(n - 2);
    }
    

    搞定,是不是很简单?

    零基础的可能还是不大懂,没关系,之后慢慢按照这个模式练习!好吧,有大佬可能在吐槽太简单了。

    案例2:小青蛙跳台阶

    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    1、第一递归函数功能

    假设 f(n) 的功能是求青蛙跳上一个n级的台阶总共有多少种跳法,代码如下:

    int f(int n){
        
    }
    

    2、找出递归结束的条件

    我说了,求递归结束的条件,你直接把 n 压缩到很小很小就行了,因为 n 越小,我们就越容易直观着算出 f(n) 的多少,所以当 n = 1时,你知道 f(1) 为多少吧?够直观吧?即 f(1) = 1。代码如下:

    int f(int n){
        if(n == 1){
            return 1;
        }
    }
    

    第三要素:找出函数的等价关系式

    每次跳的时候,小青蛙可以跳一个台阶,也可以跳两个台阶,也就是说,每次跳的时候,小青蛙有两种跳法。

    第一种跳法:第一次我跳了一个台阶,那么还剩下n-1个台阶还没跳,剩下的n-1个台阶的跳法有f(n-1)种。

    第二种跳法:第一次跳了两个台阶,那么还剩下n-2个台阶还没,剩下的n-2个台阶的跳法有f(n-2)种。

    所以,小青蛙的全部跳法就是这两种跳法之和了,即 f(n) = f(n-1) + f(n-2)。至此,等价关系式就求出来了。于是写出代码:

    int f(int n){
        if(n == 1){
            return 1;
        }
        ruturn f(n-1) + f(n-2);
    }
    

    大家觉得上面的代码对不对?

    答是不大对,当 n = 2 时,显然会有 f(2) = f(1) + f(0)。我们知道,f(0) = 0,按道理是递归结束,不用继续往下调用的,但我们上面的代码逻辑中,会继续调用 f(0) = f(-1) + f(-2)。这会导致无限调用,进入死循环

    这也是我要和你们说的,关于递归结束条件是否够严谨问题,有很多人在使用递归的时候,由于结束条件不够严谨,导致出现死循环。也就是说,当我们在第二步找出了一个递归结束条件的时候,可以把结束条件写进代码,然后进行第三步,但是请注意,当我们第三步找出等价函数之后,还得再返回去第二步,根据第三步函数的调用关系,会不会出现一些漏掉的结束条件。就像上面,f(n-2)这个函数的调用,有可能出现 f(0) 的情况,导致死循环,所以我们把它补上。代码如下:

    int f(int n){
        //f(0) = 0,f(1) = 1,f(2) = 2等价于 n<=2时,f(n) = n。
        if(n <= 2){
            return n;
        }
        ruturn f(n-1) + f(n-2);
    }
    

    有人可能会说,我不知道我的结束条件有没有漏掉怎么办?别怕,多练几道就知道怎么办了。

    看到这里有人可能要吐槽了,这两道题也太容易了吧??能不能被这么敷衍。少侠,别走啊,下面出道难一点的。

    下面其实也不难了,就比上面的题目难一点点而已,特别是第三步等价的寻找。

    案例3:反转单链表。

    反转单链表。例如链表为:1->2->3->4。反转后为 4->3->2->1

    链表的节点定义如下:

    class Node{
        int date;
        Node next;
    }
    

    虽然是 Java语言,但就算你没学过 Java,我觉得也是影响不大,能看懂。

    还是老套路,三要素一步一步来。

    1、定义递归函数功能

    假设函数 reverseList(head) 的功能是反转但链表,其中 head 表示链表的头节点。代码如下:

    Node reverseList(Node head){
        
    }
    

    2. 寻找结束条件

    当链表只有一个节点,或者如果是空表的话,你应该知道结果吧?直接啥也不用干,直接把 head 返回呗。代码如下:

    Node reverseList(Node head){
        if(head == null || head.next == null){
            return head;
        }
    }
    

    3. 寻找等价关系

    这个的等价关系不像 n 是个数值那样,比较容易寻找。但是我告诉你,它的等价条件中,一定是范围不断在缩小,对于链表来说,就是链表的节点个数不断在变小,所以,如果你实在找不出,你就先对 reverseList(head.next) 递归走一遍,看看结果是咋样的。例如链表节点如下

    我们就缩小范围,先对 2->3->4递归下试试,即代码如下

    Node reverseList(Node head){
        if(head == null || head.next == null){
            return head;
        }
        // 我们先把递归的结果保存起来,先不返回,因为我们还不清楚这样递归是对还是错。,
        Node newList = reverseList(head.next);
    }
    

    我们在第一步的时候,就已经定义了 reverseLis t函数的功能可以把一个单链表反转,所以,我们对 2->3->4反转之后的结果应该是这样:

    我们把 2->3->4 递归成 4->3->2。不过,1 这个节点我们并没有去碰它,所以 1 的 next 节点仍然是连接这 2。

    接下来呢?该怎么办?

    其实,接下来就简单了,我们接下来只需要把节点 2 的 next 指向 1,然后把 1 的 next 指向 null,不就行了?,即通过改变 newList 链表之后的结果如下:

    也就是说,reverseList(head) 等价于 ** reverseList(head.next)** + 改变一下1,2两个节点的指向。好了,等价关系找出来了,代码如下(有详细的解释):

    //用递归的方法反转链表
    public static Node reverseList2(Node head){
        // 1.递归结束条件
        if (head == null || head.next == null) {
                 return head;
             }
             // 递归反转 子链表
             Node newList = reverseList2(head.next);
             // 改变 1,2节点的指向。
             // 通过 head.next获取节点2
             Node t1  = head.next;
             // 让 2 的 next 指向 2
             t1.next = head;
             // 1 的 next 指向 null.
            head.next = null;
            // 把调整之后的链表返回。
            return newList;
        }
    
    

    这道题的第三步看的很懵?正常,因为你做的太少了,可能没有想到还可以这样,多练几道就可以了。但是,我希望通过这三道题,给了你以后用递归做题时的一些思路,你以后做题可以按照我这个模式去想。通过一篇文章是不可能掌握递归的,还得多练,我相信,只要你认真看我的这篇文章,多看几次,一定能找到一些思路!!

    我已经强调了好多次,多练几道了,所以呢,后面我也会找大概 10 道递归的练习题供大家学习,不过,我找的可能会有一定的难度。不会像今天这样,比较简单,所以呢,初学者还得自己多去找题练练,相信我,掌握了递归,你的思维抽象能力会更强!

    接下来我讲讲有关递归的一些优化。

    有关递归的一些优化思路

    1. 考虑是否重复计算

    告诉你吧,如果你使用递归的时候不进行优化,是有非常非常非常多的子问题被重复计算的。

    啥是子问题? f(n-1),f(n-2)…就是 f(n) 的子问题了。

    例如对于案例2那道题,f(n) = f(n-1) + f(n-2)。递归调用的状态图如下:

    (img-adCaaEyJ-1572163241563)(https://user-gold-cdn.xitu.io/2019/3/12/169722f31645ef25?w=729&h=444&f=png&s=88214)]

    看到没有,递归计算的时候,重复计算了两次 f(5),五次 f(4)。。。。这是非常恐怖的,n 越大,重复计算的就越多,所以我们必须进行优化。

    如何优化?一般我们可以把我们计算的结果保证起来,例如把 f(4) 的计算结果保证起来,当再次要计算 f(4) 的时候,我们先判断一下,之前是否计算过,如果计算过,直接把 f(4) 的结果取出来就可以了,没有计算过的话,再递归计算。

    用什么保存呢?可以用数组或者 HashMap 保存,我们用数组来保存把,把 n 作为我们的数组下标,f(n) 作为值,例如 arr[n] = f(n)。f(n) 还没有计算过的时候,我们让 arr[n] 等于一个特殊值,例如 arr[n] = -1。

    当我们要判断的时候,如果 arr[n] = -1,则证明 f(n) 没有计算过,否则, f(n) 就已经计算过了,且 f(n) = arr[n]。直接把值取出来就行了。代码如下:

    // 我们实现假定 arr 数组已经初始化好的了。
    int f(int n){
        if(n <= 1){
            return n;
        }
        //先判断有没计算过
        if(arr[n] != -1){
            //计算过,直接返回
            return arr[n];
        }else{
            // 没有计算过,递归计算,并且把结果保存到 arr数组里
            arr[n] = f(n-1) + f(n-1);
            reutrn arr[n];
        }
    }
    

    也就是说,使用递归的时候,必要
    须要考虑有没有重复计算,如果重复计算了,一定要把计算过的状态保存起来。

    2. 考虑是否可以自底向上

    对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。

    不过,有时候当 n 比较大的时候,例如当 n = 10000 时,那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。

    对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道

    f(1) = 1;

    f(2) = 2;

    那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来取代递归,代码如下:

    public int f(int n) {
           if(n <= 2)
               return n;
           int f1 = 1;
           int f2 = 2;
           int sum = 0;
    
           for (int i = 3; i <= n; i++) {
               sum = f1 + f2;
               f1 = f2;
               f2 = sum;
           }
           return sum;
       }
    

    这种方法,其实也被称之为递推

    最后总结

    其实,递归不一定总是从上往下,也是有很多是从下往上的,例如 n = 1 开始,一直递归到 n = 1000,例如一些排序组合。对于这种从下往上的,也是有对应的优化技巧,不过,我就先不写了,后面再慢慢写。这篇文章写了很久了,脖子有点受不了了,,,,颈椎病?害怕。。。。

    说实话,对于递归这种比较抽象的思想,要把他讲明白,特别是讲给初学者听,还是挺难的,这也是我这篇文章用了很长时间的原因,不过,只要能让你们看完,有所收获,我觉得值得!有些人可能觉得讲的有点简单,没事,我后面会找一些不怎么简单的题。最后如果觉得不错,还请给我转发 or 点赞一波!

    另外,推荐一份计算机类书单,只为让大家更加方便找到自己想要的书籍,目前已经收集了几百本了,贡献给需要的人,地址:GitHub 6K,一份覆喊各类编程书籍的书单下载

    这里帅地也整理了一些不错的算法/计算机基础的资料,送给大家:

    翻遍全网,计网、操作系统、计组相关视频被我找到了

    还有一位朋友整理的设计模式资料

    字节跳动总结的设计模式 PDF 火了,完整版开放下载!

    还有一份很不错的算法笔记

    两个月斩获 70k star,前字节大神刷题笔记

    最后,献上我备战校招的思维导图 + 提升内功的 PDF 吧

    九大思维导图助你拿到心仪的 offer

    在这里插入图片描述

    原创 PDF 助你提升基础内容,里面也有我的个人经历

    在这里插入图片描述

    下载链接:https://pan.baidu.com/s/1thH7vqBEosgRrESTUcFL2Q 密码:9x30

    如果觉得有帮助,也要记得来个赞啊,只收藏不点赞都是刷流氓,嘻嘻

    展开全文
  • 递归

    万次阅读 2019-05-10 07:38:32
    递归是一种编程模式,用于一个任务可以被分割为多个相似的更简单的任务的场景。或者用于一个任务可以被简化为一个容易的行为上更简单的任务变体。或者像我们随后会看到的,用来处理特定类型的数据结构。 当一个函数...

    递归是一种编程模式,用于一个任务可以被分割为多个相似的更简单的任务的场景。或者用于一个任务可以被简化为一个容易的行为上更简单的任务变体。或者像我们随后会看到的,用来处理特定类型的数据结构。
    当一个函数解决一个任务时,在该过程中它可以调用很多其他函数。那么当 一个函数调用自身时 ,就称其为递归

    递归的俩种思考方式:

    简单起见,我们写一个函数pow(x, n),它可以计算x的n次方,即用x乘以自身n次。

    pow(2, 2) = 4
    pow(2, 3) = 8
    pow(2, 4) = 16
    

    有俩种实现方式。
    1.迭代思路:for循环:

    function pow(x, n) {
    	let result = 1;
    	//在循环中用x乘以result
    	for (let i = 0; i < n; i++) {
    		result *= x;
    	}
    	return result;
    }
    alert(pow(2, 3));  //8
    

    2.递归思路:简化任务,调用自身:

    function pow(x, n) {
    	if (n == 1) {
    		return x;
    	} else {
    		return x * pow(x, n - 1);
    	}
    }
    alert(pow(2, 3));   //8
    

    注意递归方式完全不相同。
    当pow(x, n)被调用时,执行分为俩个分支:
    在这里插入图片描述
    1.如果n == 1 ,所有事情都会变得很简单,这叫递归的基础,因为它立即得到显而易见的结果:pow(x, 1)等于x。
    2.否者,我们可以用x * pow(x, n - 1)表示pow(x, n)。这叫做一个递归步骤:我们将任务转变为更简单的行为(x的乘法)和更简单的同类任务调用(更小的n给pow)。后面步骤继续简化直到n等于1。
    我们也可以说pow递归的调用自身直到 n == 1。
    在这里插入图片描述
    比如,为了计算pow(2, 4),递归变体经过了下面几个步骤:

    1. pow(2, 4) = 2 * pow(2, 3)
    2. pow(2, 3) = 2 * pow(2, 2)
    3. pow(2, 2) = 2 * pow(2, 1)
    4. pow(2, 1) = 2

    所以,递归生成了更简单的函数调用。

    递归一般更简洁

    递归解决方案一般比迭代更简洁。
    这里我们可以使用三元运算符?来替换if语句,从而让pow(x, n)更简洁并且可读性依然很高:

    function pow(x, n) {
    	return (n == 1) ? x : (x * pow(x, n - 1));
    }
    

    最大的嵌套调用次数(包括首次)称为递归深度。在我们的例子中,它正好等于n。
    最大递归深度受限于JavaScript引擎。我们可以确信基本是10000,有些引擎可能允许更大,但是100000很可能就超过了限制。有一些自动优化能够缓解这个([尾部调用优化]),但是它们还没有被完全支持,只能用于简单场景。
    这就限制了递归的应用,但是递归仍然被广泛使用。有很多任务使用递归思路会让代码更简单,更容易维护。

    展开全文
  • 什么是递归函数?

    万次阅读 多人点赞 2018-02-21 09:42:10
    递归函数 递归 例题 特点 效率 优点 递归函数 递归 递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身,每调用一次就进入新的一层。递归函数必须有结束条件。 当函数在一直...

    递归函数

    递归

    递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身,每调用一次就进入新的一层。递归函数必须有结束条件
    当函数在一直递推,直到遇到墙后返回,这个墙就是结束条件
    所以递归要有两个要素,结束条件与递推关系

    注:

    递归的时候,每次调用一个函数,计算机都会为这个函数分配新的空间,这就是说,当被调函数返回的时候,调用函数中的变量依然会保持原先的值,否则也不可能实现反向输出。

    例题

    1. 计算n的阶乘
    #include <stdio.h> 
    int factorial(int n)
    {
        int result;
        if (n<0)                                          //判断例外
        {
            printf("输入错误!\n");
            return 0;
        } 
        else if (n==0 || n==1)
        {
            result = 1;  //回推墙
        }
        else
        {
            result = factorial(n-1) * n;  //递推关系,这个数与上一个数之间的关系。
        }
        return result;
    }
    
    int main(){
        int n = 5;                                              //输入数字5,计算5的阶乘
        printf("%d的阶乘=%d",n,factorial(n));
        return 0;
    }
    

    程序在计算5的阶乘的时候,先执行递推,当n=1或者n=0的时候返回1,再回推将计算并返回。由此可以看出递归函数必须有结束条件

    1. 斐波那契数列

    斐波那契数列指的是这样一个数列:

    0, 1, 1, 2, 3, 5, 8, 13, 21, ···
    

    这个数列从第三项开始,每一项都等于前两项之和.

    #include <stdio.h>
    
    long fibonacci( long num )
    {
        if ( num == 0 || num == 1 )
        {
            return num;
        }
        else
        {
            return fibonacci( num -1 ) + fibonacci( num -2 );
        }
    }
    
    void main()
    {
        long number;
        puts("请输入一个正整数: ");
        scanf("%ld", &number);
        printf("斐波那契数列第%ld项为: %ld\n", number, fibonacci( number ) );
    
    }
    
    

    这里写图片描述

    1. 应用题~~

    小明为了学好英语,需要每天记单词,第一天记1个,第二天记2个依次类推,请用代码完成,算出小明第10天开始的时候会了多少个单词?

    分析:
    墙(结束条件)是“第一天记1个”
    递推关系是“第n天记的单词= 第n-1天记的单词数量+n"

    #include <stdio.h>
    /* 定义获取单词数量的函数 */
    int getWordNumber(n)
    {   
        if(n == 1)
        {
            return 1;    //回推墙
        }
        else{
            return getWordNumber(n-1)+n ;       //递推关系
        }
    }
    int main()
    {
        int num = getWordNumber(10);     //获取会了的单词数量
        printf("小明第10天记了:%d个单词。\n", num);
        return 0;
    }
    

    特点

    递归函数特点:

    1. 每一级函数调用时都有自己的变量,但是函数代码并不会得到复制,如计算5的阶乘时每递推一次变量都不同;
    2. 每次调用都会有一次返回,如计算5的阶乘时每递推一次都返回进行下一次;
    3. 递归函数中,位于递归调用前的语句和各级被调用函数具有相同的执行顺序;
    4. 递归函数中,位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反;
    5. 递归函数中必须有终止语句。
    

    一句话总结递归:自我调用且有完成状态。

    效率

    1. 系统栈(也叫核心栈、内核栈)
      是内存中属于操作系统空间的一块区域,其主要用途为: (1)保存中断现场,对于嵌套中断,被中断程序的现场信息依次压入系统栈,中断返回时逆序弹出; (2)保存操作系统子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。

    2. 用户栈
      是用户进程空间中的一块区域,用于保存用户进程的子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。
      我们编写的递归程序属于用户程序,因此使用的是用户栈。

    3. 栈溢出
      函数调用的参数是通过栈空间来传递的,在调用过程中会占用线程的栈资源。而递归调用,只有走到最后的结束点后函数才能依次退出,而未到达最后的结束点之前,占用的栈空间一直没有释放,如果递归调用次数过多,就可能导致占用的栈资源超过线程的最大值,从而导致栈溢出,导致程序的异常退出。

    综上:

    函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括:局部变量、形参、调用函数地址、返回值。那么,如果递归调用N次,就要分配N次局部变量、N次形参、N次调用函数地址、N次返回值,势必效率低.

    优点

    1. 代码简洁、清晰,易懂

    循环能干的事,递归都能干;递归能干的循环不一定能干

    对于我们,能用循环解决的,尽量不适用递归.

    展开全文
  • 递归算法讲解

    万次阅读 多人点赞 2017-06-15 22:11:51
    原作者:书呆子Rico 《递归的内涵与经典应用》 http://my.csdn.net/justloveyou_摘要: 大师 L. Peter Deutsch 说过:To Iterate is Human, to ...对一些简单的递归问题,我们总是惊叹于递归描述问题的能力和编写代

    原作者:书呆子Rico 《递归的内涵与经典应用》 http://my.csdn.net/justloveyou_

    摘要:

      大师 L. Peter Deutsch 说过:To Iterate is Human, to Recurse, Divine.中文译为:人理解迭代,神理解递归。毋庸置疑地,递归确实是一个奇妙的思维方式。对一些简单的递归问题,我们总是惊叹于递归描述问题的能力和编写代码的简洁,但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。本文剖析了递归的思想内涵,分析了递归与循环的联系与区别,给出了递归的应用场景和一些典型应用,并利用递归和非递归的方式解决了包括阶乘、斐波那契数列、汉诺塔、杨辉三角的存取、字符串回文判断、字符串全排列、二分查找、树的深度求解在内的八个经典问题。

    版权声明:

      本文原创作者:书呆子Rico
      作者博客地址:http://blog.csdn.net/justloveyou_/

    友情提示:

      若读者需要本博文相关完整代码,请移步我的Github自行获取,项目名为 SwordtoOffer,链接地址为:https://github.com/githubofrico/SwordtoOffer

    一. 引子

       大师 L. Peter Deutsch 说过:To Iterate is Human, to Recurse, Divine.中文译为:人理解迭代,神理解递归。毋庸置疑地,递归确实是一个奇妙的思维方式。对一些简单的递归问题,我们总是惊叹于递归描述问题的能力和编写代码的简洁,但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。在正式介绍递归之前,我们首先引用知乎用户李继刚(https://www.zhihu.com/question/20507130/answer/15551917)对递归和循环的生动解释:

       递归:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开它。若干次之后,你打开面前的门后,发现只有一间屋子,没有门了。然后,你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这你把钥匙打开了几扇门。

       循环:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门(若前面两扇门都一样,那么这扇门和前两扇门也一样;如果第二扇门比第一扇门小,那么这扇门也比第二扇门小,你继续打开这扇门,一直这样继续下去直到打开所有的门。但是,入口处的人始终等不到你回去告诉他答案。

       上面的比喻形象地阐述了递归与循环的内涵,那么我们来思考以下几个问题:

    什么是递归呢?
    递归的精髓(思想)是什么?
    递归和循环的区别是什么?
    什么时候该用递归?
    使用递归需要注意哪些问题?
    递归思想解决了哪些经典的问题?
    这些问题正是笔者准备在本文中详细阐述的问题。

    二. 递归的内涵

    1、定义 (什么是递归?)

       在数学与计算机科学中,递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上,递归,顾名思义,其包含了两个意思:递 和 归,这正是递归思想的精华所在。

    2、递归思想的内涵(递归的精髓是什么?)

       正如上面所描述的场景,递归就是有去(递去)有回(归来),如下图所示。“有去”是指:递归问题必须可以分解为若干个规模较小,与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决,就像上面例子中的钥匙可以打开后面所有门上的锁一样;“有回”是指 : 这些问题的演化过程是一个从大到小,由近及远的过程,并且会有一个明确的终点(临界点),一旦到达了这个临界点,就不用再往更小、更远的地方走下去。最后,从这个临界点开始,原路返回到原点,原问题解决。  

                        这里写图片描述

      
       更直接地说,递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。特别地,在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况,这也正是递归的定义所在。格外重要的是,这个解决问题的函数必须有明确的结束条件,否则就会导致无限递归的情况。

    3、用归纳法来理解递归

       数学都不差的我们,第一反应就是递归在数学上的模型是什么,毕竟我们对于问题进行数学建模比起代码建模拿手多了。观察递归,我们会发现,递归的数学模型其实就是 数学归纳法,这个在高中的数列里面是最常用的了,下面回忆一下数学归纳法。

       数学归纳法适用于将解决的原问题转化为解决它的子问题,而它的子问题又变成子问题的子问题,而且我们发现这些问题其实都是一个模型,也就是说存在相同的逻辑归纳处理项。当然有一个是例外的,也就是归纳结束的那一个处理方法不适用于我们的归纳处理项,当然也不能适用,否则我们就无穷归纳了。总的来说,归纳法主要包含以下三个关键要素:

    步进表达式:问题蜕变成子问题的表达式
    结束条件:什么时候可以不再使用步进表达式
    直接求解表达式:在结束条件下能够直接计算返回值的表达式
    事实上,这也正是某些数学中的数列问题在利用编程的方式去解决时可以使用递归的原因,比如著名的斐波那契数列问题。

    4、递归的三要素

       在我们了解了递归的基本思想及其数学模型之后,我们如何才能写出一个漂亮的递归程序呢?笔者认为主要是把握好如下三个方面:

    1、明确递归终止条件;
    
    2、给出递归终止时的处理办法;
    
    3、提取重复的逻辑,缩小问题规模。

    1). 明确递归终止条件

       我们知道,递归就是有去有回,既然这样,那么必然应该有一个明确的临界点,程序一旦到达了这个临界点,就不用继续往下递去而是开始实实在在的归来。换句话说,该临界点就是一种简单情境,可以防止无限递归。

    2). 给出递归终止时的处理办法

       我们刚刚说到,在递归的临界点存在一种简单情境,在这种简单情境下,我们应该直接给出问题的解决方案。一般地,在这种情境下,问题的解决方案是直观的、容易的。

    3). 提取重复的逻辑,缩小问题规模*

       我们在阐述递归思想内涵时谈到,递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决。从程序实现的角度而言,我们需要抽象出一个干净利落的重复的逻辑,以便使用相同的方式解决子问题。

    5、递归算法的编程模型

       在我们明确递归算法设计三要素后,接下来就需要着手开始编写具体的算法了。在编写算法时,不失一般性,我们给出两种典型的递归算法设计模型,如下所示。

    模型一: 在递去的过程中解决问题

    function recursion(大规模){
        if (end_condition){      // 明确的递归终止条件
            end;   // 简单情景
        }else{            // 在将问题转换为子问题的每一步,解决该步中剩余部分的问题
            solve;                // 递去
            recursion(小规模);     // 递到最深处后,不断地归来
        }
    }

    模型二: 在归来的过程中解决问题

    function recursion(大规模){
        if (end_condition){      // 明确的递归终止条件
            end;   // 简单情景
        }else{            // 先将问题全部描述展开,再由尽头“返回”依次解决每步中剩余部分的问题
            recursion(小规模);     // 递去
            solve;                // 归来
        }
    }

    6、递归的应用场景

       在我们实际学习工作中,递归算法一般用于解决三类问题:

       (1). 问题的定义是按递归定义的(Fibonacci函数,阶乘,…);

       (2). 问题的解法是递归的(有些问题只能使用递归方法来解决,例如,汉诺塔问题,…);

       (3). 数据结构是递归的(链表、树等的操作,包括树的遍历,树的深度,…)。

      在下文我们将给出递归算法的一些经典应用案例,这些案例基本都属于第三种类型问题的范畴。

    三. 递归与循环

       递归与循环是两种不同的解决问题的典型思路。递归通常很直白地描述了一个问题的求解过程,因此也是最容易被想到解决方式。循环其实和递归具有相同的特性,即做重复任务,但有时使用循环的算法并不会那么清晰地描述解决问题步骤。单从算法设计上看,递归和循环并无优劣之别。然而,在实际开发中,因为函数调用的开销,递归常常会带来性能问题,特别是在求解规模不确定的情况下;而循环因为没有函数调用开销,所以效率会比递归高。递归求解方式和循环求解方式往往可以互换,也就是说,如果用到递归的地方可以很方便使用循环替换,而不影响程序的阅读,那么替换成循环往往是好的。问题的递归实现转换成非递归实现一般需要两步工作:

       (1). 自己建立“堆栈(一些局部变量)”来保存这些内容以便代替系统栈,比如树的三种非递归遍历方式;

       (2). 把对递归的调用转变为对循环处理。

       特别地,在下文中我们将给出递归算法的一些经典应用案例,对于这些案例的实现,我们一般会给出递归和非递归两种解决方案,以便读者体会。

    四. 经典递归问题实战

    1. 第一类问题:问题的定义是按递归定义的

    (1). 阶乘

    /**
     * Title: 阶乘的实现 
     * Description:
     *      递归解法
     *      非递归解法
     * @author rico
     */
    public class Factorial {
        /**     
         * @description 阶乘的递归实现
         * @author rico       
         * @created 2017年5月10日 下午8:45:48     
         * @param n
         * @return     
         */
        public static long f(int n){
            if(n == 1)   // 递归终止条件 
                return 1;    // 简单情景
    
            return n*f(n-1);  // 相同重复逻辑,缩小问题的规模
        }
    
    --------------------------------我是分割线-------------------------------------
    
        /**     
         * @description 阶乘的非递归实现
         * @author rico       
         * @created 2017年5月10日 下午8:46:43     
         * @param n
         * @return     
         */
        public static long f_loop(int n) {
            long result = n;
            while (n > 1) {
                n--;
                result = result * n;
            }
            return result;
        }
    }

    (2). 斐波纳契数列

    /**
    * Title: 斐波纳契数列
    *
    * Description: 斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……
    * 在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)。
    *
    * 两种递归解法:经典解法和优化解法
    * 两种非递归解法:递推法和数组法
    *

     * @author rico
     */
    public class FibonacciSequence {
    
        /**
         * @description 经典递归法求解
         * 
         * 斐波那契数列如下:
         * 
         *  1,1,2,3,5,8,13,21,34,...
         * 
         * *那么,计算fib(5)时,需要计算1次fib(4),2次fib(3),3次fib(2),调用了2次fib(1)*,即:
         * 
         *  fib(5) = fib(4) + fib(3)
         *  
         *  fib(4) = fib(3) + fib(2) ;fib(3) = fib(2) + fib(1)
         *  
         *  fib(3) = fib(2) + fib(1)
         *  
         * 这里面包含了许多重复计算,而实际上我们只需计算fib(4)、fib(3)、fib(2)和fib(1)各一次即可,
         * 后面的optimizeFibonacci函数进行了优化,使时间复杂度降到了O(n).
         * 
         * @author rico
         * @created 2017年5月10日 下午12:00:42
         * @param n
         * @return
         */
        public static int fibonacci(int n) {
            if (n == 1 || n == 2) {     // 递归终止条件
                return 1;       // 简单情景
            }
            return fibonacci(n - 1) + fibonacci(n - 2); // 相同重复逻辑,缩小问题的规模
        }

    ——————————–我是分割线————————————-

    /**     
     * @description 对经典递归法的优化
     * 
     * 斐波那契数列如下:
     * 
     *  1,1,2,3,5,8,13,21,34,...
     * 
     * 那么,我们可以这样看:fib(1,1,5) = fib(1,2,4) = fib(2,3,3) = 5
     * 
     * 也就是说,以1,1开头的斐波那契数列的第五项正是以1,2开头的斐波那契数列的第四项,
     * 而以1,2开头的斐波那契数列的第四项也正是以2,3开头的斐波那契数列的第三项,
     * 更直接地,我们就可以一步到位:fib(2,3,3) = 2 + 3 = 5,计算结束。 
     * 
     * 注意,前两个参数是数列的开头两项,第三个参数是我们想求的以前两个参数开头的数列的第几项。
     * 
    
        * 时间复杂度:O(n)
         * 
         * @author rico       
         * @param first 数列的第一项
         * @param second 数列的第二项
         * @param n 目标项
         * @return     
         */
        public static int optimizeFibonacci(int first, int second, int n) {
            if (n > 0) {
                if(n == 1){    // 递归终止条件
                    return first;       // 简单情景
                }else if(n == 2){            // 递归终止条件
                    return second;      // 简单情景
                }else if (n == 3) {         // 递归终止条件
                    return first + second;      // 简单情景
                }
                return optimizeFibonacci(second, first + second, n - 1);  // 相同重复逻辑,缩小问题规模
            }
            return -1;
        }
    
    --------------------------------我是分割线-------------------------------------
    
        /**
         * @description 非递归解法:有去无回
         * @author rico
         * @created 2017年5月10日 下午12:03:04
         * @param n
         * @return
         */
        public static int fibonacci_loop(int n) {
    
            if (n == 1 || n == 2) {   
                return 1;
            }
    
            int result = -1;
            int first = 1;      // 自己维护的"栈",以便状态回溯
            int second = 1;     // 自己维护的"栈",以便状态回溯
    
            for (int i = 3; i <= n; i++) { // 循环
                result = first + second;
                first = second;
                second = result;
            }
            return result;
        }
    
    --------------------------------我是分割线-------------------------------------
    
    /**     
         * @description 使用数组存储斐波那契数列
         * @author rico       
         * @param n
         * @return     
         */
        public static int fibonacci_array(int n) {
            if (n > 0) {
                int[] arr = new int[n];   // 使用临时数组存储斐波纳契数列
                arr[0] = arr[1] = 1;
    
                for (int i = 2; i < n; i++) {   // 为临时数组赋值
                    arr[i] = arr[i-1] + arr[i-2];
                }
                return arr[n - 1];
            }
            return -1;
        }
    }

    (3). 杨辉三角的取值

    /**     
     * @description 递归获取杨辉三角指定行、列(从0开始)的值
     *              注意:与是否创建杨辉三角无关
    
        * @author rico 
         * @x  指定行
         * @y  指定列    
         */
      /**
        * Title: 杨辉三角形又称Pascal三角形,它的第i+1行是(a+b)i的展开式的系数。
        * 它的一个重要性质是:三角形中的每个数字等于它两肩上的数字相加。
        * 
        * 例如,下面给出了杨辉三角形的前4行: 
        *    1 
        *   1 1
        *  1 2 1
        * 1 3 3 1
        * @description 递归获取杨辉三角指定行、列(从0开始)的值
        *              注意:与是否创建杨辉三角无关
        * @author rico 
        * @x  指定行
        * @y  指定列  
        */
        public static int getValue(int x, int y) {
            if(y <= x && y >= 0){
                if(y == 0 || x == y){   // 递归终止条件
                    return 1; 
                }else{ 
                    // 递归调用,缩小问题的规模
                    return getValue(x-1, y-1) + getValue(x-1, y); 
                }
            }
            return -1;
        } 
    }

    (4). 回文字符串的判断

    /**
    * Title: 回文字符串的判断
    * Description: 回文字符串就是正读倒读都一样的字符串。如”98789”, “abccba”都是回文字符串
    *
    * 两种解法:
    * 递归判断;
    * 循环判断;
    *

     * @author rico       
     */      
    public class PalindromeString {
    
        /**     
         * @description 递归判断一个字符串是否是回文字符串
         * @author rico       
         * @created 2017年5月10日 下午5:45:50     
         * @param s
         * @return     
         */
        public static boolean isPalindromeString_recursive(String s){
            int start = 0;
            int end = s.length()-1;
            if(end > start){   // 递归终止条件:两个指针相向移动,当start超过end时,完成判断
                if(s.charAt(start) != s.charAt(end)){
                    return false;
                }else{
                    // 递归调用,缩小问题的规模
                    return isPalindromeString_recursive(s.substring(start+1).substring(0, end-1));
                }
            }
            return true;
        }
    
    --------------------------------我是分割线-------------------------------------
    
        /**     
         * @description 循环判断回文字符串
         * @author rico       
         * @param s
         * @return     
         */
        public static boolean isPalindromeString_loop(String s){
            char[] str = s.toCharArray();
            int start = 0;
            int end = str.length-1;
            while(end > start){  // 循环终止条件:两个指针相向移动,当start超过end时,完成判断
                if(str[end] != str[start]){
                    return false;
                }else{
                    end --;
                    start ++;
                }
            }
            return true;
        }
    }

    (5). 字符串全排列

    递归解法
    /**
    * @description 从字符串数组中每次选取一个元素,作为结果中的第一个元素;然后,对剩余的元素全排列

         * @author rico
         * @param s
         *            字符数组
         * @param from
         *            起始下标
         * @param to
         *            终止下标
         */
        public static void getStringPermutations3(char[] s, int from, int to) {
            if (s != null && to >= from && to < s.length && from >= 0) { // 边界条件检查
                if (from == to) { // 递归终止条件
                    System.out.println(s); // 打印结果
                } else {
                    for (int i = from; i <= to; i++) {
                        swap(s, i, from); // 交换前缀,作为结果中的第一个元素,然后对剩余的元素全排列
                        getStringPermutations3(s, from + 1, to); // 递归调用,缩小问题的规模
                        swap(s, from, i); // 换回前缀,复原字符数组
                    }
                }
            }
        }
    
        /**
         * @description 对字符数组中的制定字符进行交换
         * @author rico
         * @param s
         * @param from
         * @param to
         */
        public static void swap(char[] s, int from, int to) {
            char temp = s[from];
            s[from] = s[to];
            s[to] = temp;
        }

    非递归解法(字典序全排列)
    /**
    * Title: 字符串全排列非递归算法(字典序全排列)
    * Description: 字典序全排列,其基本思想是:
    * 先对需要求排列的字符串进行字典排序,即得到全排列中最小的排列.
    * 然后,找到一个比它大的最小的全排列,一直重复这一步直到找到最大值,即字典排序的逆序列.
    *
    * 不需要关心字符串长度
    *
    * @author rico
    */
    public class StringPermutationsLoop {

    /**
     * @description 字典序全排列
     * 
     * 设一个字符串(字符数组)的全排列有n个,分别是A1,A2,A3,...,An
     * 
     * 1. 找到最小的排列 Ai
     * 2. 找到一个比Ai大的最小的后继排列Ai+1
     * 3. 重复上一步直到没有这样的后继
     * 
     * 重点就是如何找到一个排列的直接后继:
     * 对于字符串(字符数组)a0a1a2……an,
     * 1. 从an到a0寻找第一次出现的升序排列的两个字符(即ai < ai+1),那么ai+1是一个极值,因为ai+1之后的字符为降序排列,记 top=i+1;
     * 2. 从top处(包括top)开始查找比ai大的最小的值aj,记 minMax = j;
     * 3. 交换minMax处和top-1处的字符;
     * 4. 翻转top之后的字符(包括top),即得到一个排列的直接后继排列
     * 
    
      * @author rico
         * @param s
         *            字符数组
         * @param from
         *            起始下标
         * @param to
         *            终止下标
         */
        public static void getStringPermutations4(char[] s, int from, int to) {
    
            Arrays.sort(s,from,to+1);  // 对字符数组的所有元素进行升序排列,即得到最小排列 
            System.out.println(s);    
    
            char[] descendArr = getMaxPermutation(s, from, to); // 得到最大排列,即最小排列的逆序列
    
            while (!Arrays.equals(s, descendArr)) {  // 循环终止条件:迭代至最大排列
                if (s != null && to >= from && to < s.length && from >= 0) { // 边界条件检查
                    int top = getExtremum(s, from, to); // 找到序列的极值
                    int minMax = getMinMax(s, top, to);  // 从top处(包括top)查找比s[top-1]大的最小值所在的位置
                    swap(s, top - 1, minMax);  // 交换minMax处和top-1处的字符
                    s = reverse(s, top, to);   // 翻转top之后的字符
                    System.out.println(s);
                }
            }
        }
    
        /**
         * @description 对字符数组中的制定字符进行交换
         * @author rico
         * @param s
         * @param from
         * @param to
         */
        public static void swap(char[] s, int from, int to) {
            char temp = s[from];
            s[from] = s[to];
            s[to] = temp;
        }
    
        /**     
         * @description 获取序列的极值
         * @author rico       
         * @param s 序列
         * @param from 起始下标
         * @param to 终止下标
         * @return     
         */
        public static int getExtremum(char[] s, int from, int to) {
            int index = 0;
            for (int i = to; i > from; i--) {
                if (s[i] > s[i - 1]) {
                    index = i;
                    break;
                }
            }
            return index;
        }
    
        /**     
         * @description 从top处查找比s[top-1]大的最小值所在的位置
         * @author rico       
         * @created 2017年5月10日 上午9:21:13     
         * @param s
         * @param top 极大值所在位置
         * @param to
         * @return     
         */
        public static int getMinMax(char[] s, int top, int to) {
            int index = top;
            char base = s[top-1];
            char temp = s[top];
            for (int i = top + 1; i <= to; i++) {
                if (s[i] > base && s[i] < temp) {
                    temp = s[i];
                    index = i;
                }
                continue;
            }
            return index;
        }
    
        /**     
         * @description 翻转top(包括top)后的序列
         * @author rico       
         * @param s
         * @param from
         * @param to
         * @return     
         */
        public static char[] reverse(char[] s, int top, int to) {
            char temp;
            while(top < to){
                temp = s[top];
                s[top] = s[to];
                s[to] = temp;
                top ++;
                to --;
            }
            return s;
        }
    
        /**     
         * @description 根据最小排列得到最大排列
         * @author rico       
         * @param s 最小排列
         * @param from 起始下标
         * @param to 终止下标
         * @return     
         */
        public static char[] getMaxPermutation(char[] s, int from, int to) {
            //将最小排列复制到一个新的数组中
            char[] dsc = Arrays.copyOfRange(s, 0, s.length);
            int first = from;
            int end = to;
            while(end > first){  // 循环终止条件
                char temp = dsc[first];
                dsc[first] = dsc[end];
                dsc[end] = temp;
                first ++;
                end --;
            }
            return dsc;
        }

    (6). 二分查找

    /**
    * @description 二分查找的递归实现
    * @author rico
    * @param array 目标数组
    * @param low 左边界
    * @param high 右边界
    * @param target 目标值
    * @return 目标值所在位置
    */

    public static int binarySearch(int[] array, int low, int high, int target) {
    
            //递归终止条件
            if(low <= high){
                int mid = (low + high) >> 1;
                if(array[mid] == target){
                    return mid + 1;  // 返回目标值的位置,从1开始
                }else if(array[mid] > target){
                    // 由于array[mid]不是目标值,因此再次递归搜索时,可以将其排除
                    return binarySearch(array, low, mid-1, target);
                }else{
                    // 由于array[mid]不是目标值,因此再次递归搜索时,可以将其排除
                    return binarySearch(array, mid+1, high, target);
                }
            }
            return -1;   //表示没有搜索到
        }
    
    --------------------------------我是分割线-------------------------------------
    
    /**     
         * @description 二分查找的非递归实现
         * @author rico       
         * @param array 目标数组
         * @param low 左边界
         * @param high 右边界
         * @param target 目标值
         * @return 目标值所在位置
         */
    public static int binarySearchNoRecursive(int[] array, int low, int high, int target) {
    
            // 循环
            while (low <= high) {
                int mid = (low + high) >> 1;
                if (array[mid] == target) {
                    return mid + 1; // 返回目标值的位置,从1开始
                } else if (array[mid] > target) {
                    // 由于array[mid]不是目标值,因此再次递归搜索时,可以将其排除
                    high = mid -1;
                } else {
                    // 由于array[mid]不是目标值,因此再次递归搜索时,可以将其排除
                    low = mid + 1;
                }
            }
            return -1;  //表示没有搜索到
        }
    1. 第二类问题:问题解法按递归算法实现

    (1). 汉诺塔问题

    /**
    * Title: 汉诺塔问题
    * Description:古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。
    * 有一个和尚想把这64个盘子从A座移到C座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,
    * 小盘在上。在移动过程中可以利用B座。要求输入层数,运算后输出每步是如何移动的。
    *

     * @author rico
     */
    public class HanoiTower {
    
        /**     
         * @description 在程序中,我们把最上面的盘子称为第一个盘子,把最下面的盘子称为第N个盘子
         * @author rico       
         * @param level:盘子的个数
         * @param from 盘子的初始地址
         * @param inter 转移盘子时用于中转
         * @param to 盘子的目的地址
         */
        public static void moveDish(int level, char from, char inter, char to) {
    
            if (level == 1) { // 递归终止条件
                System.out.println("从" + from + " 移动盘子" + level + " 号到" + to);
            } else {
                // 递归调用:将level-1个盘子从from移到inter(不是一次性移动,每次只能移动一个盘子,其中to用于周转)
                moveDish(level - 1, from, to, inter); // 递归调用,缩小问题的规模
                // 将第level个盘子从A座移到C座
                System.out.println("从" + from + " 移动盘子" + level + " 号到" + to); 
                // 递归调用:将level-1个盘子从inter移到to,from 用于周转
                moveDish(level - 1, inter, from, to); // 递归调用,缩小问题的规模
            }
        }
    
        public static void main(String[] args) {
            int nDisks = 30;
            moveDish(nDisks, 'A', 'B', 'C');
        }
    1. 第三类问题:数据的结构是按递归定义的

    (1). 二叉树深度

    /**
    * Title: 递归求解二叉树的深度
    * Description:
    * @author rico
    * @created 2017年5月8日 下午6:34:50
    */

    public class BinaryTreeDepth {
    
        /**     
         * @description 返回二叉数的深度
         * @author rico       
         * @param t
         * @return     
         */
        public static int getTreeDepth(Tree t) {
    
            // 树为空
            if (t == null) // 递归终止条件
                return 0;
    
            int left = getTreeDepth(t.left); // 递归求左子树深度,缩小问题的规模
            int right = getTreeDepth(t.left); // 递归求右子树深度,缩小问题的规模
    
            return left > right ? left + 1 : right + 1;
        }
    }

    (2). 二叉树深度

    /**
     * @description 前序遍历(递归)
     * @author rico
     * @created 2017年5月22日 下午3:06:11
     * @param root
     * @return
     */
    
     public String preOrder(Node<E> root) {
            StringBuilder sb = new StringBuilder(); // 存到递归调用栈
            if (root == null) {   // 递归终止条件
                return "";     // ji 
            }else { // 递归终止条件
                sb.append(root.data + " "); // 前序遍历当前结点
                sb.append(preOrder(root.left)); // 前序遍历左子树
                sb.append(preOrder(root.right)); // 前序遍历右子树
                return sb.toString();
            }       
        }
    展开全文
  • 递归递归递归递归

    千次阅读 多人点赞 2015-06-07 18:35:38
    用扩展欧几里德算法求乘法逆元的算法过程,就是对递归调用的深层理解,花了老长时间才搞懂。。 下面是我看的别人博客上的讲解 C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数 ...
  • 快速排序(三种算法实现和非递归实现)

    万次阅读 多人点赞 2017-11-29 18:41:44
    快速排序(Quick Sort)是对冒泡排序的一种改进,基本思想是选取一个记录作为枢轴,经过一趟排序,将整段序列分为...递归实现:void QuickSort(int* array,int left,int right) { assert(array); if(left &amp;gt;=
  • 10张动图学会python循环与递归

    万次阅读 多人点赞 2020-12-19 08:43:00
    图像(包括动图)是传递信息的一种高效方式,往往能增强表象、记忆与思维等方面的反应强度。所谓一图胜千言,说的就是这个道理。今天为大家整理了十张动图GIFS,有助于认识循环、递归、二分检索等...
  • Java实现简单的递归操作

    万次阅读 多人点赞 2017-04-03 11:22:48
    在数据结构算法设计中,或者一个方法的具体实现的时候,有一种方法叫做“递归”,这种方法在思想上并不是特别难,但是实现起来还是有一些需要注意的。虽然对于很多递归算法都可以由相应的循环迭代来代替,但是对于...
  • 递归算法时间复杂度分析

    万次阅读 多人点赞 2018-09-17 16:16:59
    递归算法时间复杂度分析 时间复杂度: 一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。 T...
  • 本课程带你从递归算法基础入手,课程是精讲大量实际项目中常用到的案例,课程深入浅出,包括递归入门,递归遍历、弟归穷举算法及各种项目,适合算法爱好者一起学习,后附每堂课项目源码,感兴趣可以观注博客,不定期...
  • 递归再特定的场景下,非常实用,巧妙的递归设计能解决很多问题,文章主要列出了递归的各种思想和丰富的使用案例!
  • C#递归 C#递归 C#递归

    2010-11-27 15:46:04
    C#递归C#递归C#递归C#递归C#递归C#递归C#递归C#递归C#递归
  • 递归递归递归递归递归递归递归递归递归递归
  • 10张 GIF 动图让你弄懂递归等概念

    万次阅读 多人点赞 2019-07-27 12:15:00
    点击蓝色“五分钟学算法”关注我哟加个“星标”,一起学算法来源 | 编程派今天为大家整理了十张动图GIFS,有助于认识循环、递归、二分检索等概念的具体运行情况。一、循环GI...
  • python 递归-递归可视化

    万次阅读 2020-07-10 13:44:54
    python 递归-递归可视化 文章目录python 递归-递归可视化1、实现2、递归可视化-Coding 1、实现 2、递归可视化-Coding
  • c++递归c++递归c++递归

    2011-08-19 17:43:00
    c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘...
  • JS函数递归

    万次阅读 多人点赞 2016-12-30 18:47:24
    本博客主要讲述关于JS的函数递归,主要从“变量+函数”和“函数+变量”两个方面说明解释。
  • 彻底理解递归,从递归的本质说起!

    万次阅读 多人点赞 2018-05-12 14:28:35
    比较简单地方式就是用递归去遍历,鉴于递归这种调用方法有一定的特殊性,今天还是想来讲讲怎么去理解递归遍历。本文针对想理解递归的过程的朋友,因为本人在学到这一部分的时候也纠结了很久,其实只要理解了过程,那...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,301,975
精华内容 520,790
关键字:

递归