精华内容
下载资源
问答
  • 关于递归

    2014-03-03 22:48:00
     一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算...

    递归算法

      程序调用自身的编程技巧称为递归( recursion)。 
      一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
       注意:
       (1) 递归就是在过程或函数里调用自身;
       (2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。

      一个比较经典的描述是老和尚讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在讲故事,他说从前有座山, ……。这样没完没了地反复讲故事,直到最后老和尚烦了停下来为止。

      反复讲故事可以看成是反复调用自身,但如果不能停下来那就没有意义了,所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有,最后老和尚烦了停下来这样的递归的终止条件也要有。

    阶乘的算法可以定义成函数

    当 n>0时,用 f(n-1)来定义 f(n),用 f(n-1-1)来定义 f(n-1)……,这是对递归形式的描述。

    当 n=0时, f(n)=1,这是递归结束的条件。

    其实所有的递归问题都可以看成是阶层问题

    所要解决的整个问题(整个递归函数)看成是 f(n).在这个递归函数中要做到如下几点:

      *1.写出递归的出口
      *2.解决当前要解决的问题-----相当与阶层问题中的(n)
      *3.递归下去(调用自身)解决相同的但规模要小的又一问题-----相当于f(n-1)

    如果函数实现了这几点,那么递归算法也就基本成功.

    不过有些问题他的f(n-1)可能要调用几次(可能每次的参数还不同),因为他在实现(n)的时候要先调用f(n-1)为前提,

    这样的例子很多.比如梵塔问题就是这种情况.

    总而言之,你要懂的把复杂的递归问题迁移成简单的阶层递归问题,这时候问题就比较好理解和解决.

    下面是几个用递归解决问题的几个例子

    一.用递归的算法把数组中的N个数按颠倒的次序重新存放。

    经过上面的方法来分析得出程序如下:

    package sf.digui;

    public class Recursion{
     private int b[]=null;
     private int len=0;
     public Recursion(int b[]){
      this.b=b;
      this.len=b.length;
      }
      
      public void resevert(int i,int j){
       if(i>=j) return;
       //====================
       b[i]=b[i]+b[j];
       b[j]=b[i]-b[j];//注意:这里没有通过第三方(另开内存)来实现两个变量的值交换
       b[i]=b[i]-b[j];
       //=========================
       
       resevert(i+1,j-1);
       }
       
       public void printThis(){
        
        for(int i=0;i<len;i++){
         System.out.print(b[i]+" ");
         
         }
         System.out.println();
        }
        
        
        public static void main(String[] args){
         int b[]={1,2,3,4,5,6,7,8,9};
         int len=b.length;
         Recursion rec=new Recursion(b);
         System.out.println("数组起始的数为:");
         rec.printThis();
         rec.resevert(0,len-1);
         System.out.println("数组经过倒转之后的数为:");
         rec.printThis();
         }
     }

    二..用递归算法完成:有52张牌,使它们全部正面朝上,第一轮是从第2张开始,凡是2的倍数位置上的牌翻成正面朝下;第二轮从第3张牌开始,凡是3的倍数位置上的牌,正面朝上的翻成正面朝下,正面朝下的翻成正面朝上;第三轮从第4张牌开始,凡是4的倍数位置上的牌按上面相同规则翻转,以此类推,直到第一张要翻的牌超过52为止。统计最后有几张牌正面朝上,以及它们的位置号。

    经过上面的方法分析,得出程序如下:

    package sf.digui;

    public class DiGui{
     private int n;
     //private int a;
     private int p[]=null;//存放所有牌的正反面信息
     public DiGui(int n){
      this.n=n;
      //a=n;
      p=new int[n];
      for(int i=0;i<n;i++){
       p[i]=0;//这里0表示是正面,1表示是反面
       }
      }
      
      
      public void process(int a){//======相当于f(n)
       int b=a;
       if(a==1) return;// 递归的出口
      //下面部分为解决当前要做的(可以从最后一步或第一步着手思考要做的事)---相当与(n)
      //===================================================     
        while(b<=n){//
         p[b-1]=(p[b-1]==0)?1:0;//
         b=2*b;//
         }
      //====================================================  
        process(a-1);//调用自身,解决相同的但规模要小的又一问题---相当于f(n-1)
        
        
       }
       
       public void printThis(){
        process(n);
        for(int i=0;i<n;i++){
         System.out.println("第"+(i+1)+"张的正反面序号为:"+p[i]);
         }
        }
        
        
        public static void main(String[] args){
         DiGui digui=new DiGui(52);
         digui.printThis();
         }
     }
     
     
     /*说明:
      *我认为所有递归都可看成像阶层一样的问题---相当于f(n)=n+f(n-1),都要做递归函数中
      *解决如下几个问题:
      *1.写出递归的出口
      *2.解决当前要解决的问题-----相当与阶层问题中的(n)
      *3.递归下去(调用自身)解决相同的但规模要小的又一问题-----相当于f(n-1)
      *
      *
      *要学会把复杂的递归问题迁移成像阶层一样简单的递归问题

      **/

     

    转载于:https://www.cnblogs.com/zhanpang/p/5682917.html

    展开全文
  • 关于递归的理解

    2020-12-01 22:25:48
    关于递归的理解1.递归的理解1)递归的概念2)递归的三大要素①明确函数要干什么②寻找递归结束条件③找出函数的等价关系式④举些例子2.递归之八皇后问题理解3.递归的优化1)尾调用2)memoization3)函数式编程(Java...

    1.递归的理解

    1)递归的概念

    一种计算过程,如果其中每一步都要用到前一步或前几步的结果,称为递归的。用递归过程定义的函数,称为递归函数,例如连加、连乘及阶乘等。凡是递归的函数,都是可计算的,即能行的 。

    古典递归函数,是一种定义在自然数集合上的函数,它的未知值往往要通过有限次运算回归到已知值来求出,故称为“递归”。它是古典递归函数论的研究对象 。

    通俗来说就是一种形式,不断调用一个函数,如在点外卖时候,会点开炒饭区如果没有想要吃的,就点开煮面区,一直重复到点好外卖为之 。

    2)递归的三大要素

    ①明确函数要干什么

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

    我们定义了一个算n的阶乘的函数,
    传入是一个int型整数,输出也是一个int型整数
    功能就是计算n的阶乘
    int f(int n){
        计算n的阶乘;
        return n的阶乘;
    }
    

    ②寻找递归结束条件

    所谓递归,就是会在函数内部代码中,调用这个函数本身,所以,我们必须要找出递归的结束条件,不然会一直调用自己,直到栈溢出。也就是说,我们需要找出参数变化为何值时的条件使得递归结束,再把结果返回,这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。

    先拆分为几小步
    int f(int n){
        //当传入的是1,我们能很清楚知道1的阶乘是1
        if(n == 1){
            return 1;
        }
        //当传入的是2,我们能很清楚知道2的阶乘是2*1=2
        if(n == 2){
            return 2*1;//等价于return 2;
        }
        //当传入的是3,我们能很清楚知道2的阶乘是3*2*1=6
        if(n == 3){
            return 3*2*1;
        }
        //结合一下找到递归结束的条件就是n<=2
        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)。
    ​
    int f(int n){
        //结合一下找到递归结束的条件就是n<=2
        if(n <= 2){
            return n;
        }
        //把f(n)的等价操作写进来
        return f(n-1)*n;
    } 
    

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

    这就是递归最重要的三要素,也就是每次做递归的时候,可以试着去寻找这三个要素。

    ④举些例子

    各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)

    各种算法中也会使用到递归,比如快排,归并排序,二分查找,分治算法等.

    将用栈解决的问题–>递归代码比较简洁

    1.斐波那契数列

    问题:斐波那契数列的是这样一个数列:112358132134…,即第一项 f(1) = 1,第二项 f(2) = 1,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。
      
      第一步,写出递归函数和功能
    我们定义了一个算n的阶乘的函数,
    传入是一个int型整数,输出也是一个int型整数
    功能就是求第n项的值
    int f(int n){
        计算第n项的值;
        return 第n项的值;
    }
    ​
      第二步找出递归结束的条件
    int f(int n){
        //当传入的是1,我们能很清楚知道求第1项的值是1
        if(n == 1){
            return 1;
        }
        //当传入的是1,我们能很清楚知道求第2项的值是1
        if(n == 2){
            return 1;
        }
        //当传入的是3,我们能很清楚知道第3项的值是2
        if(n == 3){
            return 2;
        }
        //结合一下找到递归结束的条件就是n<=2
        if(n <= 2){
            return 1;
        }
    }
    ​
      第三步,找出函数等价条件关系式
    题目已经把等价关系式给我们了,很容易就能够知道 f(n) = f(n-1) + f(n-2)int f(int n){
        //结合一下找到递归结束的条件就是n<=2
        if(n <= 2){
            return 1;
        }
        //加入等价式
        return f(n-1) + f(n - 2);
    }
    

    2.小青蛙跳台阶

    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
      
      第一步,写出递归函数和功能
    我们定义了一个算n的阶乘的函数,
    传入是一个int型整数,输出也是一个int型整数
    功能就是求青蛙跳上一个n级的台阶总共有多少种跳法
    int f(int n){
        青蛙跳上一个n级的台阶总共有多少种跳法;
        return 青蛙跳上一个n级的台阶总共有多少种跳法;
    }
    ​
      第二步找出递归结束的条件
    int f(int n){
        //当传入的是1,我们能很清楚知道求青蛙跳上一个1级的台阶总共有1种跳法
        if(n == 1){
            return 1;
        }
        //当传入的是1,我们能很清楚知道求青蛙跳上一个2级的台阶总共有2种跳法
        if(n == 2){
            return 2;
        }
        //当传入的是3,我们能很清楚知道求青蛙跳上一个3级的台阶总共有3种跳法
        if(n == 3){
            return 3;
        }
        //结合一下找到递归结束的条件就是n==1
        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){
        //结合一下找到递归结束的条件就是n<=2
        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)。
    这会导致无限调用,从而进入死循环。
    也就是说,我们要补上n=0的条件
    int f(int n){
        //经过分析,f(2)=2也是一个临界条件。
        if(n <= 2){
            return n;
        }
        ruturn f(n-1) + f(n-2);
    }
    

    3.反转单链表

    问题:反转单链表。例如链表为:1->2->3->4。反转后为 4->3->2->1
      
      第一步,写出递归函数和功能
    我们定义了一个算n的阶乘的函数,
    传入是一个单链表头节点,输出也是一个单链表头节点
    功能就是反转单链表
    先来个链表节点
    class Node{
        Object date;
        Node next;
    }
    Node f(Node head){
        反转单链表;
        return 反转后的单链表节点;
    }
    ​
      第二步找出递归结束的条件
    容易可以得出链表只有一个节点或者是一张空表时候结束递归
    Node f(Node head){
        if(head == null || head.next == null){
            return head;
        }
    }
    ​
      第三步,找出函数等价条件关系式
    2->3->4 递归成 4->3->21这个节点我们并没有去碰它,所以1的next节点仍然是连接2。
    只需要把节点2的next指向1,然后把1的next指向 null就行了。
    f(head) 等价于 f(head.next) + 改变一下12两个节点的指向。
    Node f(Node node){
        if(head == null || head.next == null){
            return head;
        }
        //递归反转子链表 
        Node newList = f(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; 
    }
    

    2.递归之八皇后问题理解

      八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。
    该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:
    在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,
    即任意两个皇后都不能处于同一行、同一列或同一斜线上,
    问有多少种摆法。 
      高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,
      后来有人用图论的方法解出92种结果。
      计算机发明后,有多种计算机语言可以解决此问题
    
    八皇后问题是典型的回溯法解决的问题。
    

    所谓回溯法,名字高大上,思想很朴素。设想把你放在一个迷宫里,想要走出迷宫,最直接的办法是什么呢?没错,试。先选一条路走起,走不通就往回退尝试别的路,走不通继续往回退,直到找到出口或所有路都试过走不出去为止。这就是暴力破解。盲僧李青说得好:如果暴力不是为了解题,那就毫无意义了。

    尽管回溯法也算是暴力方法,但也不是特别暴力

    从8*8=64个格子里选8个格子,放皇后,测试是否满足条件,若满足则计数加1,否则换8个格子继续试。

    很显然, 64中选8,并不是个小数字,有着十亿级别的尝试次数

    稍加分析,我们可以得到一个不那么暴力的办法,显然,每行每列最多只能有一个皇后,如果基于这个事实进行暴力破解,那结果会好得多。安排皇后时,第一行有8种选法,一旦第一行选定,假设选为(1,i),第二行只能选(2,j),其中j!=i,所以有7种选法。以此类推,需要穷举的情况有8!=40320种。

    看起来这个结果已经不错了,但尝试的次数是随问题规模按阶乘水平提高的,8皇后太多了,把问题缩成4皇后,4个皇后在4*4的格子里各自安排不打架,一共有多少种安排方法?
    在这里插入图片描述
    试着穷举,4!=24次,我们真的需要24次尝试吗?

    现在我们把第一个皇后放在第一个格子,被涂黑的地方是不能放皇后的。
    在这里插入图片描述
    第二行的皇后只能放在第三格或第四格,比方我们放第三格,则:

    在这里插入图片描述
    前两位皇后沆瀣一气,已经把第三行全部锁死了,第三位皇后无论放哪里都难逃被吃掉的厄运。于是在第一个皇后位于1号,第二个皇后位于3号的情况下问题无解。我们只能返回上一步来,给2号皇后换个位置。
    在这里插入图片描述
    显然,第三个皇后只有一个位置可选。当第三个皇后占据第三行蓝色空位时,第四行皇后无路可走,于是发生错误,返回上层调用(3号皇后),而3号也别无可去,继续返回上层调用(2号),2号已然无路可去,继续返回上层(1号),于是1号皇后改变位置如下,继续搜索
    在这里插入图片描述
    到这,“回溯法”便是谓知易行难

    基本思路是:

    1.第一行先占一个皇后

    2.第二行再占一个且不能与第一个皇后攻击

    3.第三行再占一个

    n.第n行占一个,当第n行站不下的时候,取消n-1行的皇后,在第n-1皇后的下一个位置重新占一个皇后位置,知道占到最n-1行的最后一个位置,当还不行的时候,就取消第n-2行,当n-2行的皇后在n-2行的最后一个位置的时候,就取消n-3,n-2在最后一个位置,那么n-3行的一定不再最后一个位置

    再重新寻找n-2行的皇后的位置

    直到找到最后一个皇后

    package com.atguigu.queen8;public class Queen8 {// 一共有多少个皇后(此时设置为8皇后在8X8棋盘)
    int max = 8;
    // 该数组保存结果,第一个皇后摆在array[0]列,第二个摆在array[1]列
    int[]  array = new int[max];
    static int  count = 0;
    public static void main(String[] args) {
    ​
    Queen8 queen8 = new Queen8();
    queen8.check(0);
    System.out.println("一共有" + count + "种解法");
    }/**
         * n代表当前是第几个皇后 [n 是从 0 开始算的,即0 表示第一个皇后, 同时n也表示第几行]
         * 即 第1行是第一个皇后(n=0),第2行是第二个皇后(n=1), 第8行是第8个皇后(n=7),如果遍历到第9行(n=8),说明
         * 皇后全部放置好了, 就相应的得到了一种解法... 
         * 然后回溯 ,又将第一个皇后,放置第1行的第2列...
         * @param n
         * 皇后n在array[n]列
         */
        private void check(int n) {
            //终止条件是最后一行已经摆完,
        //由于每摆一步都会校验是否有冲突,
        //所以只要最后一行摆完,说明已经得到了一个正确解
            if (n == max) {
                print();
                return;
            }
            //将第n个皇后从.第一列开始放值,然后判断是否和本行本列本斜线有冲突,如果OK,就进入下一行的逻辑
            for (int i = 0; i < max; i++) {
                array[n] = i; //先将第一个皇后放置第一行的第一列 array[0] = 0
                if (judge(n)) {  // 如果 该皇后没有和其它皇后冲突
                    check(n + 1); // 放第二个皇后,因为是递归,因此大家可以思考,第二个皇后是从 第二行的第1列开始放
                }
            }
        }
        
        /**
         * 查看n皇后是否满足约束条件(即:检查皇后n是否会发生冲突) 
         * 如果冲突,返回 false , 如果不冲突返回true
         * 0 4 7 5 2 6 1 3 
         * @param n
         * @return
         */
        private boolean judge(int n) {
            for (int i = 0; i < n; i++) {
            //说明: 
            //1. array[i] == array[n] 判断 是不是在同一列
            //2. Math.abs(n - i) == Math.abs(array[n] - array[i]) 判断是不是在同一条斜线
            //3. 不用判断是不是在同一行,因为我们每放一个皇后,行是递增的.
                if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                    return false;
                }
            }
            return true;
        }
        /**
         * 打印这个满足条件的八皇后的放置位置
         */
        private void print()  {
        count++;
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }
    }

    3.递归的优化

    递归的优点:

    书写:简洁
    使用:在树的前序,中序,后序遍历算法中,递归的实现明显要比循环简单得多。
    

    递归的缺点:

    性能:假设传入的参数值特别大,那么这个调用栈将会非常之大,最终可能超出调用栈的缓存大小而崩溃导致程序执行失败。每一次函数调用会在内存栈中分配空间,而每个进程的栈的容量是有限的,当调用的层次太多时,就会超出栈的容量,从而导致栈溢出。
    效率:
    递归由于是函数调用自身,而函数调用是有时间和空间的消耗的:每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间。
    递归中很多计算都是重复的,由于其本质是把一个问题分解成两个或者多个小问题,多个小问题存在相互重叠的部分,则存在重复计算,如fibonacci斐波那契数列的递归实现。
    

    1)尾调用

    尾递归是一种递归的写法,可以避免不断的将函数压栈最终导致堆栈溢出。通过设置一个累加参数,并且每一次都将当前的值累加上去,然后递归调用。通过尾递归,我们可以把复杂度从O(n)降低到O(1),是指一个函数里的最后一个动作是返回一个函数的调用结果的情形,即最后一步新调用的返回值直接被当前函数的返回结果。
    (注意:**JVM仍然不支持尾调用优化,**因此对大多数Java开发人员来说,Java不进行尾调用优化并不是什么大问题。不过我猜或许很多Java程序员都没有听说过尾调用优化这回事。不过当你在JVM上运行函数式语言的话,这就成为一个问题了。递归的代码在自己语言的解释器里运行得好好的,可能一到JVM上就突然把栈给用完了。)

    以下用js代码为例

    //核心:就是看一个函数在调用另一个函数得时候,本身是否可以被“释放”
    function f(x) {
      a(x)
      b(x)
      return g(x) //函数执行的最后调用另一个函数
    }
    

    任何的尾调用,不只是尾递归,函数调用本身都可以被优化掉,变得跟goto操作一样。这就意味着,在函数调用前先把栈给设置好,调用完成后再恢复栈的这个操作(分别是prolog和epilog)可以被优化掉。比如说下面的这段代码:

    函数调用栈和调用帧为例
    函数的调用层数非常多时,调用栈会消耗大量内存,甚至栈溢出,造成程序严重卡顿或意外崩溃。
    function f(x) {
      res = g(x)
      return res+1
    }
    ​
    function g(x) {
      res = r(x)
      return res + 1
    }
    ​
    function r(x) {
      res = x + 1
      return res + 1
    }
    
    尾调用解决栈溢出风险
    调用g之后,和f就没有任何关系了,函数f就结束了,
    所以执行到最后一步,完全可以删除 f() 的调用记录,
    只保留 g(30) 的调用记录。
    function f() {
      m = 10
      n = 20
      return g(m + n)
    }
    f()// 等同于
    function f() {
      return g(30)
    }
    f()// 等同于
    g(30)
    

    将函数优化为尾调用,那么完全可以做到每次执行时,调用帧为一,这将大大节省内存,提高能效。

    说到递归,尾递归=尾调用+递归

    function factorial(n, total = 1) {
      // console.trace()
      if (n === 0) {
        return total
      }return factorial(n - 1, n * total)
    }
    调用如下
    factorial(3, 1) 
    factorial(2, 3) 
    factorial(1, 6) 
    factorial(0, 6) 
    // n = 0; return 6
    

    调用栈不再需要多次对factorial进行压栈处理,因为每一个递归调用都不在依赖于上一个递归调用的值。因此,空间的复杂度为o(1)而不是0(n)。

    2)memoization

    (引自https://www.cnblogs.com/lalalagq/p/9906621.html)

    简单来说,memoization 是一种优化技术,主要用于通过存储昂贵的函数调用的结果来加速计算机程序,并在再次发生相同的输入时返回缓存的结果。

    不使用 memoization

    不假思索,我们会立即写下如下的代码:

    const factorial = n =&gt; {
        if (n === 1) {
            return 1
        } else {
            return factorial(n - 1) * n
        }
    };
    

    使用memoization

    const cache = []
    const factorial = n =&gt; {
        if (n === 1) {
            return 1
        } else if (cache[n - 1]) {
            return cache[n - 1]
        } else {
            let result = factorial(n - 1) * n
            cache[n - 1] = result
            return result
        }
    };
    

    使用 闭包 和 memoization

    常见的方式是 闭包 和 memoization 一起搭配使用:

    const factorialMemo = () =&gt; {
        const cache = []
        const factorial = n =&gt; {if (n === 1) {
                return 1
            } else if (cache[n - 1]) {
                console.log(`get factorial(${n}) from cache...`)
                return cache[n - 1]
            } else {
                let result = factorial(n - 1) * n
                cache[n - 1] = result
                return result
            }
        }
        return factorial
    };
    const factorial = factorialMemo();
    

    memorization 可以把函数每次的返回值存在一个数组或者对象中,在接下来的计算中可以直接读取已经计算过并且返回的数据,不用重复多次相同的计算。是一个空间换时间的方式,这种方法可用于部分递归中以提高递归的效率。

    3)函数式编程(Java描述):尾调用及抽象递归

    一个有趣的解释,递归就是包子馅的包子,它的极限是个馒头。即便Java不支持尾调用优化,但我们并不想浪费尾递归带来的便利,《Java函数式编程》一书提供了一个非常好的思路,把递归进一步抽象出来,将在栈上的递归改为在堆上的递归。

    public static int sum(int n, int acc) {
        if (n == 0){
          return acc;
          }
        else {
          acc = acc + n;
          return sum(n - 1, acc);
          }
    }
    

    这是一个符合尾递归的函数

    但把参数给个1000,会爆栈

    只是因为Java不支持尾调用优化,也就是jvm虚拟机不支持这个。

    现在,我们来进一步抽象递归操作。

    我们定义一个类TailCall来表示递归操作,其中泛型T表示递归操作的结果类型。递归分为两个部分,一个是中间调用,另一个就是最终结果,因此我们需要两个子类表示这些过程。即用Return表示最后一个调用,它是提供结果的,所以直接持有一个T类型的变量;Suspend表示中间的递归调用,为我们提供调用链上的某一部操作,持有Supplier实例。很明显,这是一个用链表表示的栈结构(LIFO),每一个节点存储每一步调用步骤。

    public abstract class TailCall<T> {
        private TailCall() {
        }
        public static class Return<T> extends TailCall<T> {
        private final T t;
        public Return(T t) {
           this.t = t;
        }
     }
     public static class Suspend<T> extends TailCall<T> {
        private final Supplier<TailCall<T>> resume;
        public Suspend(Supplier<TailCall<T>> resume) {
             super();
             this.resume = resume;
        }
     }
    }
    ​
    ​
    我们抽象出几个方法来表示这两个子类的操作:
        public abstract TailCall<T> resume();
        //返回调用链上的某一中间步骤
        public abstract T eval();
        //返回结果
        public abstract boolean isSuspend();
        //是否是一个中间操作
        对于Return类来说:
        @Override
        public TailCall<T> resume() {
          throw new IllegalStateException("return has no resume!");
        }
        //我表示的是一个最终调用产生的结果,所以我没必要支持此操作,直接抛出异常。
        @Override
        public T eval() {
          return t;
        }
        //返回储存的结果
        @Override
        public boolean isSuspend() {
          return false;
        }
        //我不是一个中间调用过程,返回false。而对于Suspend类:
        @Override
        public TailCall<T> resume() {
          return resume.get();
        }
        //返回调用链的下一个TailCall.
        @Override
        public T eval() {
          TailCall<T> tailCall = this;
          while (tailCall.isSuspend()) {
             tailCall = tailCall.resume();
          }
          return tailCall.eval();
        }
        //通过不断在调用链上遍历,找到最终的结果。
        @Override
        public boolean isSuspend() {
           return true;
        }
       //Suspend表示我是一个中间操作
    

    完整代码

    public abstract class TailCall<T> {
        public abstract TailCall<T> resume();
        public abstract T eval();
        public abstract boolean isSuspend();
        private TailCall() {
        }
        public static <T> Return<T> ret(T t) {
            return new Return<T>(t);
        }
        public static <T> Suspend<T> sus(Supplier<TailCall<T>> s) {
            return new Suspend<>(s);
        }
        public static class Return<T> extends TailCall<T> {
            private final T t;
        public Return(T t) {
            this.t = t;
        }
        @Override
        public TailCall<T> resume() {
            throw new IllegalStateException("return has no resume!");
        }
        @Override
        public T eval() {
            return t;
        }
        @Override
        public boolean isSuspend() {
            return false;
        }
     }
     
     public static class Suspend<T> extends TailCall<T> {
           private final Supplier<TailCall<T>> resume;
           public Suspend(Supplier<TailCall<T>> resume) {
               super();
               this.resume = resume;
           }
           @Override
           public TailCall<T> resume() {
               return resume.get();
           }
           @Override
           public T eval() {
               TailCall<T> tailCall = this;
               while (tailCall.isSuspend()) {
                   tailCall = tailCall.resume();
               }
               return tailCall.eval();
           }
           @Override
           public boolean isSuspend() {
               return true;
           }
          }
    }
    public static int sum(int n, int acc) {
          return sum0(n, acc).eval();
    }
    public static TailCall<Integer> sum0(int n, int acc) {
          return n == 0 ? ret(acc) : sus(() -> sum0(n - 1, acc + n))//将两个工厂方法静态导入
    }
    

    尽管可以,当使用函数式语言在JVM上进行开发的时候,也要避免使用过深的递归调用。

    4.递归的调用机制(简单版)

    图出自https://www.bilibili.com/video/BV1E4411H73v
    如图所示:当调用test(4)方法时,会在栈内存中独立开辟一个新的栈,接着调用test(4)方法时会再独立开辟一个新的栈直到不需要再次调用。

    ​ 可以看到,一个函数每次被调用时,都会在内存中创建一个帧,来包含函数的局部变量和参数,对于递归函数,栈上可能同时存在多个函数帧。当每调用一次函数f(n)时,栈顶指针就会往栈顶移动一个位置,直到满足退出递归的条件(n==1).之后再依次返回当前的结果直接,栈顶指针往下移动。

    递归,也就是先“递”后“归”。
    

    这时要说到递归的调用规则

    1. 程序执行一个函数时,就创建一个新的受保护的独立空间(新函数栈) 。

    2. 函数的局部变量是独立的,不会相互影响 。

    3. 递归必须向退出递归的条件逼近,否则就是无限递归 。

    4. 当一个函数执行完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁 。

    例:

    求函数值:
    已知 f(1)=3; f(n) = 2*f(n-1)+1; 请使用递归的思想编程,求出f(n)的值.
    用递归来做的话便是:
    f(4)=2 * f(3) + 1
    f(4)=2 * (2 * f(2) + 1) + 1
    f(4)=2 * (2 * (2 * f(1) + 1) + 1) + 1
    f(4)=2 * (2 * (2 * 3 + 1) + 1) + 1
    f(4)=2 * 15 + 1
    f(4)=31
    

    5.递归的调用机制(复杂版)

    1)基于栈的本质

    (引自:https://blog.csdn.net/dashuniuniu/article/details/50347149)

    例如执行”a = b + c”,在基于栈的虚拟机上字节码指令如下所示:

    I1: LOAD C 
    I2: LOAD B 
    I3: ADD 
    I4: STORE A
    

    由于操作数都是隐式地,所以指令可以做的很短,一般都是一个或者两个字节。但是显而易见就是指令条数会显著增加。而基于寄存器虚拟机执行该操作只有一条指令:

    I1: add a, b, c
    

    其中a,b,c都是虚拟寄存器。操作数栈上的变化如下图所示:

    首先从符号表上读取数据压入操作数栈,
    在这里插入图片描述
    然后从栈中弹出操作数执行加法运算,这步操作有物理机器执行,如下图所示:
    在这里插入图片描述

    2)递归的工作栈

    (引自https://www.cnblogs.com/yangyuliufeng/p/9211412.html)

    IA-32使用栈来支持过程的嵌套调用。每个过程都有自己的栈区,称为栈帧(stack frame) 。因此,一个栈由若干栈帧组成,每个栈帧用专门的帧指针寄存器EBP指定起始位置,当前栈帧的范围在其和栈指针寄存器ESP指向区域之间。

    IA-32规定,寄存器EAX、ECX和EDX是调用者保存寄存器。当过程P调用过程Q时,Q 可以直接使用这三个寄存器,不用将它们的值保存到栈中,这也意味着,如果P在从Q返回后还要用这三个寄存器的话,P应在转到Q之前先保存它们的值,并在从Q返回后先恢复它们的值再使用。寄存器EBX、ESl、EDI是被调用者保存寄存器,Q必须先将它们的值保存到栈中再使用它们,并在返回P之前先恢复它们的值。

    (1)每次递归调用前,先将参数n~参数1按序复制到调用过程栈帧中

    (2)执行call指令:首先将返回地址(call指令要执行时EIP的值,即call指令下一条指令的地址)压入栈顶,然后将程序跳转到当前调用的方法的起始地址,相当于执行了push和jump指令。

    递归调用时,每一层调用过程栈帧中存放的返回地址都是相同的。

    (3)每次递归,必定要先push %ebp(把原帧指针保存在栈顶)和mov %esp,%ebp(把存放原帧指针的栈顶,设置为新栈底)

    被调用者定义的非静态局部变量仅存放于当前栈帧,调用结束后就被释放了。

    最后往往通过EAX寄存器将结果返回给调用者。

    (4)执行leave指令:将栈指针指向帧指针,然后pop备份栈顶存放的原帧指针到EBP。

    (5)最后执行ret指令:将栈顶的返回地址弹出到EIP,然后按照EIP此时指示的指令继续执行程序。
    在这里插入图片描述
    如图所示,Q的过程体执行时,入口参数1的地址总是R[ebp]+8,入口参数2的地址总是R[ebp]+12……(在栈中传递的参数若是基本类型,则都被分配4个字节)

    与IA-32不同,x86-64最多可有6个整型或指针型参数通过寄存器传递,超过6个入口参数时,后面的通过栈来传递。在栈中传递的参数若是基本类型,则都被分配8个字节。栈中的地址也变为了8个字节。

    RAX、R10和R11为调用者保存寄存器。RBX、RBP、R12、R13、R14和R15为被调用者保存寄存器,需要将它们先保存在栈中再使用,最后返回前再恢复其值。
    在这里插入图片描述
    过程调用中使用的栈机制和寄存器使用约定,使得可以进行过程的嵌套调用和递归调用。
    在这里插入图片描述

    3)递归的底层

    (以下转载于https://www.cnblogs.com/syw-casualet/p/5223595.html)

    以c和汇编的程序为例
    在这里插入图片描述

    
    pushl %ebp  //压栈,压入一个栈顶元素并存到寄存器ebp中
    movl %esp, %ebp  //将ebp内存单元中的数据传给esp,让esp = ebp,栈顶指针等于栈底指针
    subl $4, %esp  //esp=esp-4,即esp向下移动4个单位,相当于开辟了1个局部int,同时默认了ebp为栈底
    

    这三条用于保存栈的信息,ebp寄存器指向栈底,esp寄存器指向栈顶,栈底是高地址而栈底是低地址。执行完这三行后,栈就为main开辟了一个新空间,新空间从ebp开始到esp结束。

    开辟前与开辟后寄存器的位置关系如下图:
    在这里插入图片描述
    当main执行完后,我们需要消除它的栈,并返回原来的状态,如何返回呢?通过保存ebp=100这个信息。所以我们返回ebp=100,esp=88。这也就是为什么要做上面这三个步骤。然后继续,movl  $8,(%esp) ,将数值8放在esp所指向的位置。
    在这里插入图片描述
    接下来进入被调用函数f,利用到call指令,这里讲一下call指令的作用。常见的CPU的CALL指令(“调用”指令)的功能,就是以下两点:

    (1)将下一条指令的所在地址(即当时程序计数器PC的内容)入栈

    (2)将子程序的地址送入PC(即开始执行子程序)

    这时候会将EIP寄存器压入栈(EIP用来存储CPU要读取指令的地址), eip指向的是call的下一条指令,,addl $1, %eax(eax是X86汇编语言上cpu通用的寄存器名称,是32位寄存器,用来暂时存储数值或地址),随后进入函数并执行头三行:

    pushl %ebp
    movl %esp, %ebp
    subl $4, %esp
    

    在这里插入图片描述

    
    movl    8(%ebp) , %eax
    movl    %eax , (%esp)
    call    g
    

    继续看调用函数f的代码,第一行表示将ebp+8地址所在位置的值放入eax中,而由图解可知ebp+8的值实际上是8。这儿的8又正好是C语言里f(int x)的参数传递。所以,在32位X86的情况下,函数的参数传递是通过栈来实现的。我们在用call命令调用函数之前,先把需要的参数压入栈,然后再使用call命令将eip压栈,然后进入新的函数后,旧的ebp压栈,新的ebp指向的位置存了这个刚压栈的旧的ebp,所以我们可以通过新的ebp指向的位置,通过计算得到函数需要的参数值。接下来,movl  %eax, (%esp) ,会把eax的值放入esp所指向的内存的位置,然后调用 g函数,,又可以压入call指令的下一条指令的地址。
    在这里插入图片描述
    在这里插入图片描述
    进行g函数,执行前两条指令,得到的结果如下:
    在这里插入图片描述
    被调用函数g的第三条指令,movl  8(%ebp), %eax ,与之前的代码一致,将ebp+8位置的值存储在eax中。第四条指令,将eax+3,此时eax = 11。第五条指令,popl  %ebp,将栈顶的那个数取出并存入到ebp寄存器中,ebp变成了72,因为这个时候esp执行的位置存放的值就是72,而这个值也是上一个函数中ebp的值。所以得到下图:
    在这里插入图片描述
    然后ret执行,ret执行时会把栈顶元素弹到eip中,即把在这里leave的地址弹到eip中,就可以执行leave 指令了,得到的图是:
    在这里插入图片描述
    leave 指令类似一条宏指令, 等价于movl %ebp, %esp  popl %ebp。由已知,ebp=72中存取的值是84,这又是上一个的旧ebp的值,所以继续leave,弹出,得到下图:
    在这里插入图片描述
    这一步后,又遇到了一次ret,开始执行addl  $1,%eax,由于之前的eax=11,所以现在变成了12。然后又碰到了leave指令,弹出,达到清栈的目的。效果图如下:
    在这里插入图片描述
    于是栈恢复了状态。此时main中2还剩下一条ret指令,由于之前一开始我们没考虑过main的地址压栈,所这部分问题留给操作系统。

    总结:

    一个函数的执行过程,会有自己的一段从ebp 到esp的栈空间。对于一个函数,ebp指向的位置的值是调用这个函数的上一个函数的栈空间的ebp的值, 这种机制使得leave指令可以清空一个函数的栈、达到调用之前的状态。由于在这个栈设置之前,有一个eip压栈的过程,所以leave 以后的ret正好对应了上一个函数的返回地址,也就是返回上一个函数时要执行的指令的地址,另外,由于对于一个函数的栈空间来说,ebp指向的位置存了上一个ebp的值, 再往上是上一个函数的返回地址,再往上是上一个函数压栈传参数的值,所以我们知道了自己的当前ebp,就可以通过栈的机制来获得参数。

    展开全文
  • 关于递归函数转换非递归函数的一些方式前言目的可行性转换的几种途径 前言 最近在重拾算法和数据结构的一些知识,打算从基本的树的遍历算法入手。网上翻看了很多的二叉树的遍历算法相关文章,二叉树的遍历有前、中、...

    前言

    最近在重拾算法和数据结构的一些知识,打算从基本的树的遍历算法入手。网上翻看了很多的二叉树的遍历算法相关文章,二叉树的遍历有前、中、后三种遍历方法。最简单的用递归方法遍历,三种方法的逻辑一目了然很好理解,看到非递归遍历方法时,前序遍历还能理解,中序和后序遍历看的理解起来感觉不那么顺了,所以想先研究一下递归方法改非递归方法的一些方法,翻看了一些文章结合自己的理解记录下对递归方法改成非递归方法的一些方法。

    目的

    既然是要将递归方法转换成非递归方法,那首先就要明白为什么要将递归方法转换成非递归方法,也就是递归转非递归的目的和意义何在?如果这样的转换没有任何实际意义那也就不存在转换的必要了。下面收集了一些递归和非递归方法的一些优缺点,自己权衡:

    1. 递归函数逻辑清楚,以数学化的方式来写函数,便于理解。非递归函数一般相对逻辑性和可理解性要差些。
    2. 大部分语言的编译器对递归的层数有限制。非递归函数没有这个限制。当然有时间和性能上的要求。
    3. 递归方式使用了系统的栈来存储函数的参数和变量等,造成额外的更多的开销。 非递归方式要分情况考虑系统开销,后面例子测试会有比较。

    可行性

    既然清楚了递归函数转换成非递归函数的目的,下面就要提出一个问题,那就是是否所有的递归函数都能转换成非递归函数即转换的可行性。这个答案是肯定的。一个显然的原因是:我们计算机是如何运行递归函数的?学习过汇编语言的童鞋可以很自然的理解这个原因。汇编语言中对函数的调用通过call指令来执行, call指令通过将调用程序段执行的寄存器及代码执行计数器入栈的方式来执行被调用函数,被调用函数执行完毕后通过return指令来出栈。所以原则上我们可以借助栈这个结构用程序来模拟函数调用过程,也就是可以实现非递归转换成递归的方法。

    转换的几种途径

    递归转换成非递归一般有以下几种途径:

    1. 可行性里面介绍了借助栈来实现转换。
    2. 使用循环和数组方式来转换。

    这两种方法效率不同,且循环数组方式不一定能解决所有的转换问题,查阅网上的一些资料可以参考:

    1. 公众号:Linux云计算网络的 : 漫谈递归转非递归.
    2. 奔跑de五花肉的: 递归算法转换为非递归算法的技巧.

    转换示例

    第一个例子:阶乘n!

    由易入难首先选择阶乘,n的阶乘计算方法: n! = n * (n-1) * (n-2) * … * 3 * 2 * 1 (n>0且n属于自然数),它也可以是一个最简单的递归函数,假设f(n)=n!,则f(n)=n * f(n-1),f(1) = 1,那么写成递归代码如下(本文代码均用Python描述):

    # 递归求阶乘 n>0
    def recu_fact(n):
    	if n==1:
    		return 1
    	else:
    		return n * recu_fact(n-1)
    

    这个递归函数就是尾递归函数,我们可以很自然的使用循环来改写成非递归结构,代码如下:

    # 非递归方式求阶乘,循环数组方法改写
    def cycle_fact(n):
    	result = 1
    	for i in range(1, n+1):
    		result = result * i
    	return result
    

    然后,我们用栈模拟方式来改写成非递归结构,python中的list有append()和pop()方法实际上可以看成栈,但是为了便于理解,我们先定义一个文件stack.py来模拟一个栈类,代码如下:

    #!/usr/bin/python
    # coding:utf-8
    # stack.py
    # 使用列表封装的一个简易Stack类,便于演示算法
    
    class Stack(object):
    	def __init__(self):
    		self._list = []
    	
    	# 压栈	
    	def push(self, node):
    		self._list.append(node)
    	
    	# 出栈
    	def pop(self):
    		return self._list.pop()
    	
    	# 栈是否为空
    	def empty(self):
    		return len(self._list) == 0
    	
    	# 栈顶元素	
    	def top(self):
    		return self._list[-1]
    	
    	def __len__(self):
    		return len(self._list)
    

    push(), pop(),empty(),top()是栈常用的几个方法,不多解释。
    然后尝试用栈模拟来变更成非递归方法,代码如下:

    # 非递归阶乘计算
    # n>0; n=1:f(1)=1, n>1:f(n)=n*f(n-1)
    # 理解last和top指针的作用,cmp(last,top)决定是压栈还是出栈		
    def nonrecu_fact(n):
    	# 定义一个类来存储函数的参数和返回值
    	class ret(object):
    		n = 0			# 函数参数
    		result = None		# 函数返回值
    		def __init__(self, n):
    			self.n = n
    	#pdb.set_trace()
    	stack = Stack()
    	r = ret(n)
    	stack.push(r)	
    	last = r	# 每一次push的时候要设置last为栈顶元素
    	while not stack.empty():
    		top = stack.top()
    		if top.n == 1:
    			top.result = 1
    			last = stack.pop()	# 每一次pop要设置last,pop意味着栈顶函数已经解出
    		else:
    			if last == top:	# 两者一致说明上一层的函数未解出,所以需要压栈
    				r = ret(top.n-1)
    				stack.push(r)
    				last = r
    			else:
    				m = last.result
    				top.result = m * top.n
    				last = stack.pop()
    	return last.result
    

    这里解释下:

    1. 建立类ret主要用来保存函数的参数和返回值,可以想象一下函数调用过程,函数参数如何传给调用函数,返回值又如何提供给调用函数。
    2. 循环的结束靠栈是否为空判断。
    3. 循环外栈中压入第一个对象。
    4. 通过last和top指针的比较来判断是压栈还是出栈。

    第二个例子:菲波那契数列

    斐波那契数列又叫兔子数列,它的由来和那个经典的数学题有关:每对大兔每个月能生产1对小兔,而每对大兔生长2个月就成为大兔,假设初始只有1对小兔,求n个月后兔子的对数。数学表示:n个月兔子的对数为F(n),则F(n)=F(n-1)+F(n-2),显然F(1)=F(2)=1,这就是Fibonacci数列的公式。递归函数求解逻辑很自然,代码如下:

    # 递归fibonacci数 n>0 
    def recu_fib(n):
    	if n<=2:
    		return 1
    	else:
    		return recu_fib(n-1) + recu_fib(n-2)
    

    下面寻找转换为非递归的方法,首先考虑循环数组方式,代码如下:

    # 非递归计算fibonacci数列,循环数组方式
    def cycle_fib(n):
    	x = [1] * n
    	for i,value in enumerate(x):
    		if i>=2:
    			x[i] = x[i-1] + x[i-2]
    	return x[-1]
    

    使用栈模拟方式转换,代码如下:

    # 非递归计算fibnacci数列,栈模拟方式
    def nonrecu_fib(n):
    	# 定义类存储函数的参数和返回值
    	class ret(object):
    		n = 0,		# 存储形参
    		n1 = None	# 内部变量,存储f(n-1)
    		n2 = None	# 内部变量,存储f(n-2)
    		result = None	# 存储返回值
    		def __init__(self, n):
    			self.n = n
    
    	stack = Stack()
    	r = ret(n)
    	stack.push(r)
    	last = r	
    	while not stack.empty():
    		top = stack.top()
    		if top.n in (1,2):
    			top.result = 1
    			last = stack.pop()
    		else:
    			if last == top:	
    				if top.n1 == None:		# top.f(n-1)还未算出,继续push下一层
    					r = ret(top.n-1)
    					stack.push(r)
    					last = r
    				else:					# top.f(n-1)已解出,开始计算top.f(n-2), push f(n-2)
    					r = ret(top.n-2)
    					stack.push(r)
    					last = r
    			else:
    				m = last.result
    				if top.n1 == None:
    					top.n1 = m
    					last = top	# 此处一定要设置last和top一致
    				else:
    					top.n2 = m
    					top.result = top.n1 + top.n2
    					last = stack.pop()
    	return last.result
    

    效率的比较

    1、阶乘三种方式函数的执行效率比较

    首先比较阶乘的三种方式所用的时间,代码如下:

    # 导入时间模块用于计算程序运行时间
    import time	
    def main():
    	t0 = time.clock()
    	f1 = [recu_fact(i) for i in range(1, 15)]
    	t1 = time.clock()
    	f2 = [cycle_fact(i) for i in range(1, 15)]
    	t2 = time.clock()
    	f3 = [nonrecu_fact(i) for i in range(1, 15)]
    	t3 = time.clock()
    	print(f1)
    	print(f2)
    	print(f3)
    	print('recu method: %fms'%((t1-t0)*1000))
    	print('cycle method: %fms'%((t2-t1)*1000))
    	print('nonrecu method: %fms'%((t3-t2)*1000))
    

    在开始测试前,我预估了一下结果应该是:数组循环方式最快,递归和栈模拟方式最慢,但是两则时间应该差不多。但是 结果打脸了,😓 调用main函数,实际运行结果如下:
    三种方式求阶乘运行结果
    运行时间:循环数组方式<递归<栈模拟。 最让我觉得不可思议的地方是栈模拟方式慢了那么多。会不会是巧合?多次运行后结果差不多,改代码全部运行F(i)(i取值100,200,300等)也是如此,单次运行大概栈模拟的时间大概是递归时间的4-2倍左右,运行时间次数越多,越趋向于2倍,递归是循环数组方式的6倍左右。修改代码并使用matplolib画图,代码如下:

    # 导入时间模块用于计算程序运行时间
    import time	
    
    # 导入matplotlib和numpy用于画图
    import matplotlib.pyplot as plt
    import numpy as np
    def main():
    	x = np.linspace(100,900,9)
    	y1 = []
    	y2 = []
    	for i in x:
    		i = int(i)
    		t0 = time.clock()
    		f1 = recu_fact(i)	
    		t1 = time.clock()
    		f2 = cycle_fact(i)	
    		t2 = time.clock()
    		f3 = nonrecu_fact(i)	
    		t3 = time.clock()
    		
    		e1 = (t1-t0)*1000
    		e2 = (t2-t1)*1000
    		e3 = (t3-t2)*1000
    		print(i, e1, e2, e3)
    		y1.append(e1/e2) 	# 以循环数组方式运行时间为基准,递归相对于循环数组的花费时间
    		y2.append(e3/e2)	# 以循环数组方式运行时间为基准,栈模拟相对于循环数组的花费时间
    	
    	plt.plot(x,y1)
    	plt.plot(x,y2)
    	plt.show()
    

    运行结果如下:
    以循环素组运行方式为基准,集中方法运行时间的对比
    X轴是F(x)中的x取值,取了100,900之间每隔100的9个离散值,黄线是以循环数组方式运行耗费时间为基准,栈模拟方式运行时间耗费,蓝色的线是以循环数组方式运行耗费时间为基准,递归方式运行时间耗费。由于python对递归深度的默认限制大概是998次,所以没有计算F(1000)以后的情况了。从图中看,黄色线是逼近蓝色线的,我猜测之所以造成用栈模拟方式花费时间比递归时间高这么多的原因在于python编译器对递归的优化比我手工使用列表栈的方式更优化。此测试也可以看出,系统对递归函数的调用深度有限制。但是使用栈模拟的方式确没有这个限制,只要机器的运行速度和内存可以跟的上的话,例如调用recu_fact(1000)会报递归深度超过最大值错误,我的电脑调用nonrecu_fact(2000)确没有任何问题。当然,还有另外一种方式修改python的默认递归深度的最大值的方式,这不细说了。

    2、Fibonacci三种方式函数的执行效率比较

    其实结果应该和第一点的运行效率比较结果大致一致,这里不多说了,直接放测试代码如下:

    # 导入时间模块用于计算程序运行时间
    import time	
    def main():
    	
    	t0 = time.clock()
    	g1 = [cycle_fib(i) for i in range(1, 30)]
    	t1 = time.clock()
    	g2 = [recu_fib(i) for i in range(1, 30)]
    	t2 = time.clock()
    	g3 = [nonrecu_fib(i) for i in range(1, 30)]
    	t3 = time.clock()
    	print(g1)
    	print(g2)
    	print(g3)
    		
    	print('cycle method: %fms'%((t1-t0)*1000))
    	print('recu method: %fms'%((t2-t1)*1000))
    	print('nonrecu method: %fms'%((t3-t2)*1000))
    

    运行结果如下:
    三种方式求fibnacci数列效率比较
    以上比较结果更显著,不多说。

    总结

    从上面的测试及分析可以看出:

    1. 循环数组方式转换递归方法效率最高,这其实是一种空间换时间的方法,但是,并不适合所有的递归转换。
    2. 递归方式简单明了,逻辑清楚,但是一般语言的编译器对递归深度有限制。
    3. 栈模拟的方式转换递归,可以转换所有的递归,这其实是一种使用栈结构来模拟底层函数调用的一种实现。但是也存在逻辑上不够清楚的缺陷,但是能绕过一般语言编译器上对递归深度的限制。效率上没有编译器的优化,效率最差。

    所以用不用递归,应该视具体问题而言,各种选择都有优劣。在循环数组方式逻辑清楚的情况下用循环数组方式其实更好的照顾了执行效率和代码的可读性。 如果在必须用递归的情况下,尽可能的使用一种叫尾递归的方法改造递归函数,尾递归其实是在递归函数的一种优化的表示,原则上可以使用更少的栈空间,但是可读性上也要稍差,可以参考下面对尾递归的介绍:
    怀念小兔: 递归和尾递归.

    说明

    调试的方法

    python程序测试过程中都会用到调试,使用最多的可能是打印日志的方法,但是使用pdb调试效率会更高,例如本篇,我为了测试递归函数和我写的栈模拟的区别使用了pdb调试,pdb调试一般有两种方法:

    1. cmd下加载代码,命令:python -m pdb recursive.py 进入pdb后设置断点等。
    2. 在程序中import pdb,在需要设置断点的地方使用:pdb.set_trace()
      单步调试指令n,进入函数s. 百度搜索"python pdb"等可以得到更多指令,不细说。

    完整的代码

    完整的测试代码见本文附件资源。

    展开全文
  • --------------------------------------以下错误的------------------------------- #include #include #include #include using namespace std; int m; int n,in[100]; int flag=0; void pd(int in[],int n,...
  • 递归

    千次阅读 2016-04-22 11:57:39
    递归方法具有易于描述、证明简单等优点,在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用,是许多复杂算法的基础。 递归概念 一个函数在它的函数体内调用它自身称为递归(recursion)调用。是一个...
    1. 递归概述
      递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题,是分治策略的具体体现。
      递归方法具有易于描述、证明简单等优点,在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用,是许多复杂算法的基础。
    2. 递归概念
      一个函数在它的函数体内调用它自身称为递归(recursion)调用。是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法,通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂

    3. 递归步骤
      递归需要有边界条件递归前进段递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
      使用递归要注意以下几点:
      (1)递归就是在过程或函数里调用自身;
      (2)在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。
      int r(int a)
      {
      b=r(a−1);
      return b;
      }
      这个函数是一个递归函数,但是运行该函数将无休止地调用其自身,这显然是不正确的。为了防止递归调用无终止地进行,必须在函数内有终止递归调用的手段。常用的办法是加条件判断,满足某种条件后就不再作递归调用,然后逐层返回。
      构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的,也可以是递推描述的。

    4. 递归难点
      1、函数被调用返回时,返回到调用它的下一条汇编语句
      2、递归也是如此,递归调用时返回到上一次递归调用的下一条汇编语句
      3、递归调用时,每个递归函数都有自己的一个栈帧,数据互不影响
      4、递归调用时没有被执行到的语句(也就是递归返回语句)还是调用前的状态
    5. 实例分析
      用递归法计算n!。
      n!的计算是一个典型的递归问题。使用递归方法来描述程序,十分简单且易于理解。
      (1)描述递归关系
      递归关系是这样的一种关系。设{U1,U2,U3,…,Un,…}是一个序列,如果从某一项k开始,Un和它之前的若干项之间存在一种只与n有关的关系,这便称为递归关系。
      注意到,当n≥1时,n!=n*(n−1)!(n=0时,0!=1),这就是一种递归关系。对于特定的k!,它只与k与(k−1)!有关。
      (2)确定递归边界
      在步骤1的递归关系中,对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界(或递归出口)。在本例中,递归边界为k=0,即0!=1。对于任意给定的N!,程序将最终求解到0!。
      确定递归边界十分重要,如果没有确定递归边界,将导致程序无限递归而引起死循环。例如以下程序
    #include <stdio.h>
    int f(int x)
    { 
        return(f(x−1));
    }
    int main()
    { 
        printf(f(5));
        return 0;
    }
    

    它没有规定递归边界,运行时将无限循环,会导致错误
    (3)写出递归函数并译为代码
    将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示,即
    n!= n*(n−1)! 当n>1时
    n!= 1 当n=1时
    再将这种关系翻译为代码,即一个函数:

    long f(int n)
    { 
        long g;
        if(n<0)  
            printf("n<0, 输入错误!");
        else if(n==1) 
            g=1;
        else 
            g=n*f(n−1);
        return(g);
    }
    

    (4)完善程序
    主要的递归函数已经完成,设计主程序调用递归函数即可。

    #include <stdio.h>
    long f(int n)
    {
        long g;
        if(n<0)  
            printf("n<0,输入错误!");
        else if(n==1) 
            g=1;
        else 
            g=n*f(n-1);
        return(g);
    }
    int main()
    {
        int n;
        long y;
        scanf("%d",&n);
        y=f(n);
        printf("  %d!=%ld \n",n,y);
        return 0;
     }
    

    程序中给出的函数f是一个递归函数。主函数调用f后即进入函数f执行,如果n<0,n==0或n=1时都将结束函数的执行,否则就递归调用f函数自身。由于每次递归调用的实参为n−1,即把n−1的值赋予形参n,最后当n−1的值为1时再作递归调用,形参n的值也为1,将使递归终止,然后可逐层退回。
    下面我们再举例说明该过程。设执行本程序时输入为5,即求 5!。在主函数中的调用语句即为y=f(5),进入f函数后,由于n=5,不等于0或1,故应执行f=f(n−1)*n,即f=f(5−1)*5。该语句对f作递归调用即f(4)。
    进行4次递归调用后,f函数形参取得的值变为1,故不再继续递归调用而开始逐层返回主调函数。f(1)的函数返回值为1,f(2)的返回值为1*2=2,f(3)的返回值为2*3=6,f(4) 的返回值为6*4=24,最后返回值f(5)为24*5=120。
    综上,得出构造一个递归方法基本步骤,即描述递归关系、确定递归边界、写出递归函数并译为代码,最后将程序完善。

    展开全文
  • 我想,没有比下面这个例子更能形象简单的描述递归啦!请大家看下面这个在数学里常见的函数: 这是一个函数的常见表达形式,他代表着1、2、3、4、……、n-1、n这个数列。通常我们想求得除了n=1以外的任意一...
  • 关于递归的资料整理

    千次阅读 2012-07-15 21:00:46
    时隔一年,又重新学数据结构二叉树部分,被各种递归搞得苦不堪言,以下是网上资料的一些汇总整理 函数的递归调用与分治策略 递归方法是算法和程序设计中的一种重要技术。递归方法即通过函数或过程调用自身将...
  • 一.递归概念 递归算法(英语:...这几周做了一些递归的练习,对递归有了一些理解和体会,因此写在这里做一下总结,如果哪里有不对之处,烦请指出。 二.递归特点 (1)递归的使用就是不断的调用自身 (2)使用递...
  • 理解递归

    2019-04-12 08:31:54
    什么是递归 递归(英语:Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。 什么时候用递归 如果一个问题可以分解为多个子问题,每个子问题只是规模不同但解法是一致的,并且分解到最后有...
  • 递归入门

    2017-10-25 21:11:22
    写在前面: 对于强大的递归。要想做到灵活运用,是需要花时间进行练习并总结。往往递归学习的入门也是难度也比较大,常常...在此推荐一本学习递归较好的的入门书:《程序设计抽象思想:C语言描述》 。本文章也引用
  • 递归在JAVA中是指方法本身调用自己,以此来解决问题普通循环不太容易解决的问题。 递归能解决一些特定的问题,但相对的也有其缺点。递归运行速度较慢,在递归调用过 程中系统为每一层返回点,局部量等提供栈来存储...
  • 算法精解-C语言描述 递归和尾递归 (图解+实例)

    千次阅读 多人点赞 2017-10-19 06:07:23
    递归是一种强大的方法,它允许一个对象以其自身更小的形式来定义自己。 让我们来观察一下自然界中出现的递归现象:蕨类植物的叶子,每片叶子叶脉中的小分支都是整片叶子的较小缩影;又或者两个反光的物体,相互映射...
  • 递归

    2018-01-17 18:35:00
    如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在...
  • Java 递归

    2021-01-15 00:53:48
    1、递归 递归:将大问题化解为小问题的过程 说明 处理答案问题的方式和处理小问题的方式是一样的。 需要推导出一个递归公式。 1. 调用自己本身 2. 有一个趋于终止的条件 例1:递归求 N 的阶乘 public ...
  • 递归调用

    2015-07-19 14:35:36
    今天cf遇见了一点问题,是自己学过却不怎么熟悉的递归调用。...这种功能为递归结构问题提供了求解的实现手段,使程序语言的描述与问题的自然描述完全一直,因而使程序易于理解、易于维护。  通过简单的例子说明递归
  • 周世杰算法思维是计算思维的一个方面,而在计算机科学中,基于递归和迭代的思维方式在算法和程序设计中广泛应用,是算法思维的重要构成部分。因此,信息技术学科教师在基础课教学中辨析递归与迭代算法,将其作为发展...
  • 栈与递归

    2021-04-11 11:54:16
    递归是算法设计中最常用的手段,它通常将一个大型复杂问题的描述和求解变得简洁和清晰。因此递归算法常常比非递归算法更容易设计,尤其是当问题本身或所涉及的数据结构是递归定义的时候,使用递归方法更加合适。 ...
  • 关于汉诺塔问题的过程分析以及递归递归两种解法的推理
  • 递归入门 Java

    千次阅读 2016-06-07 17:08:37
    对于强大的递归。要想做到灵活运用,是需要花时间进行练习并总结。往往递归学习的入门也是难度也比较大,常常会处于看得明,却写不出的"尴尬"情况。 递归的定义 将一个大的问题分解成比较小的、有着相同形式的...
  • 递归是程序设计中很重要的技巧,简单易于实现;但递归程序效率较之非递归低得多,递归函数要直接或间接...关于递归程序转非递归程序,基本通用方法是用自定义栈结构模拟递归过程,这种方法就是万金油,几乎所有递归...
  • 递归与回溯算法

    2018-12-06 13:41:41
      最近在看数据结构时,发现了很多关于递归回溯的问题,特别是在学习了树和图等非线性结构后,对递归回溯的问题也有了一些更深的认识。接下来我们来一起看看这二者的关系如何?   递归,是一种算法结构,,一个...
  • 漫谈递归

    2013-05-27 20:13:00
    递归一词还较常用于描述以自相似方法重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。 语言例子 从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 62,843
精华内容 25,137
关键字:

以下关于递归描述错误的是