精华内容
下载资源
问答
  • 递归一词还较常用于描述以自相似方法重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。正式的定义在数学和计算机科学中,当一类对象或...

    递归,又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

    9339e8139ebe4ed25453d4c9039208f4.png

    正式的定义

    34bb01078ab6ae94595c72596baacf91.png

    在数学和计算机科学中,当一类对象或方法可以由两个属性定义时,它们表现出递归行为:

    简单的基线条件---不使用递归产生答案的终止情况

    一组规则将所有其他情形缩减到基线条件

    例如,以下是某人祖先的递归定义:

    某人的父母是他的祖先(基线条件)

    某人祖先的祖先也是他的祖先(递归步骤)

    斐波那契数列是递归的经典例子:

    Fib(0) = 1 基线条件1;

    Fib(1) = 1 基线条件2;

    对所有整数n,n > 1时:Fib(n) = (Fib(n-1) + Fib(n-2))。

    许多数学公理基于递归规则。例如,皮亚诺公理对自然数的形式定义可以描述为:0是自然数,每个自然数都有一个后继数,它也是自然数。通过这种基线条件和递归规则,可以生成所有自然数的集合。

    递归定义的数学对象包括函数、集合,尤其是分形。

    递归还有多种开玩笑的“定义”。

    非正式定义

    f7800b5558877c1ddc9b754c88e9b516.png

    递归是当程序的一个步骤涉及调用程序本身的过程。经历递归的过程被称为“递归”。

    要理解递归,必须认识到程序和程序运行之间的区别。程序是基于一组规则的一组步骤。程序的运行实际上包括遵循规则和执行步骤。一个类比:一个程序就像一个书面的食谱;运行一个程序就像实际准备饭菜一样。

    递归与过程规范中对其他程序执行的引用相关,但不相同。例如,食谱可能指烹饪蔬菜,而需要依次加水等步骤是另一个程序。然而,递归过程是指(至少)其中一个步骤需要一个相同过程的新实例,就像酸面团配方需要上次制作相同配方时剩下的一些面团。这立即产生了一个无限循环的可能性;如果为了程序能够完成,在某些情况下跳过有问题的步骤,这样递归只能在定义中被正确使用,比如一个酸面团配方,它还告诉您如何获取一些生面团,以防您以前从未做过生面团。即使定义正确,递归过程对人类来说也不容易执行,因为它需要区分过程的新调用和旧调用(部分执行);这需要对程序的各种同步实例的进展程度进行一些管理。因此,递归定义在日常情况下非常罕见。一个例子可以是下面的寻找迷宫之路的过程,继续前进,直到到达出口或分支点(死角被认为是带有0个分支的分支点)。如果到达的点是出口,终止。否则,递归地使用该过程,依次尝试每个分支;如果每次试验都只到达死胡同而失败,返回到导致这个分支点的路径并报告失败。这是否真正定义了终止过程取决于迷宫的性质:它不允许循环。在任何情况下,执行该过程都需要仔细记录所有当前探索的分支点,以及哪些分支已经被彻底尝试过。

    在语言中

    语言学家诺姆·乔姆斯基和其他许多人都认为,一种语言中语法句子数量没有上限,语法句子长度也没有上限(超出了实际的限制,例如说出来的时间),这可以解释为自然语言中递归的结果。 这可以用句法范畴的递归定义来理解,例如句子,一个句子可以有一个结构,在这个结构中,跟在动词后面的是另一个句子:多萝西认为女巫是危险的,在这个结构中,女巫是危险一句出现在更大的句子中。因此,一个句子可以递归地(非常粗略地)定义为一个结构,包括一个名词短语、一个动词和可选的另一个句子。这实际上只是递归数学定义的一个特例。

    这提供了一种理解语言创造的方法——无限数量的语法句子——因为它立即预言句子可以是任意长度的:多萝西认为托托怀疑铁皮人说的....除了可以递归定义的句子之外,还有许多结构,因此一个句子可以通过许多方式将一个类别的实例嵌入另一个类别。多年来,一般来说,语言都被证明适合这种分析。

    然而,最近,丹尼尔·埃弗雷特基于他对皮拉汉语的主张,对递归是人类语言的一个基本属性这一普遍接受的观点提出了挑战。Andrew Nevins, David Pesetsky 和 Cilene Rodrigues是许多反对这一观点的人之一。 在任何情况下,文学自我引用都可以被认为不同于数学或逻辑递归。

    递归不仅在语法中起着至关重要的作用,在自然语言语义中也是如此。例如,单词and可以理解为一种功能,它可以应用于句子含义,从而创造出新的句子,同样也可以用于名词短语含义、动词短语含义和其它。它也适用于不及物动词、及物动词或双及物动词。为了给它提供一个适当灵活的单一表示,并且通常被定义为使得它可以将这些不同类型的含义中的任何一种作为参数。这可以通过为一个简单的案例定义它来实现,在这个案例中,它组合了句子,然后根据简单的案例递归地定义其他案例。

    递归语法是一种包含递归生成规则的形式语法。

    递归幽默

    递归有时在计算机科学、程序设计、哲学或数学教科书中幽默地使用,通常是通过给出循环定义或自我引用,在循环定义或自我引用中,假定的递归步骤不会更接近基线条件,而是导致无限回归。这样的书在词汇表中包含一个笑话条目并不罕见,大致如下:

    另一个笑话是“要理解递归,你必须理解递归。” 在谷歌网络搜索引擎的英文版本中,当搜索“递归”时,网站会提示“你的意思是:递归?”Andrew Plotkin的另一种形式如下:“如果你已经知道递归是什么,就记住答案。否则,找一个比你更靠近道Douglas Hofstadter 的人;然后问他或她什么是递归。”

    递归首字母缩写也可以是递归幽默的例子。例如,PHP代表“PHP Hypertext Preprocessor”,WINE代表“WINE Is Not an Emulator.”,GNU代表“GNU's not Unix”。

    在数学中

    1042bece889d94354068fb5db31d58a3.png递归定义的集合

    例子:自然数

    递归定义集合的典型例子由自然数给出:

    0是自然数;

    如果n是自然数,那么n+1也是自然数;

    自然数集合是满足前两个属性的最小集合。

    例子:真正可达命题的集合

    另一个有趣的例子是公理系统中所有“真正可达”命题的集合。

    如果一个命题是公理,它就是一个真正可达的命题。

    如果一个命题可以通过推理规则从真正可达命题中获得,那么它就是真正可达命题。

    真正可达命题集是满足这些条件的最小命题集。

    这个集合被称为“真正可达命题”,因为在数学基础的非建设性方法中,真正命题的集合可能大于由公理和推理规则递归构造的集合。有限细分规则

    有限细分规则是递归的几何形式,可用于创建类似分形的图像。细分规则从由有限多个标签标记的多边形集合开始,然后以仅依赖于原始多边形标签的方式将每个多边形细分为更小的标记多边形,这个过程可被迭代。创建康托集合的标准“中间三分之一”技术是细分规则,重心细分也是细分规则。函数递归

    一个函数可以根据自身被部分地定义。一个常见的例子是斐波那契数列: F(n) = F(n − 1) + F(n − 2)。为了使这样的定义有用,它必须引入非递归定义的值,在这种情况下,F(0) = 0,F(1) = 1。

    一个著名的递归函数是阿克曼函数,它不同于斐波那契数列,如果没有递归,它将无法被表达的。涉及递归定义的证明

    如前几节所述,将标准的案例证明技术应用于递归定义的集合或函数,会产生结构归纳法,这是数学归纳法的一种强有力的推广,广泛用于数学逻辑和计算机科学中的推导证明。递归优化

    动态规划是一种优化方法,它以递归的形式重述了多阶段或多步骤优化问题。动态规划的关键结果是贝尔曼方程(Bellman equation),它将优化问题早期(或较早步骤)的值写入到后期(或较晚步骤)的值中。递归定理

    在集合论中,这是一个保证递归定义函数存在的定理。给定一个集合X,集合X中的一个元素a和一个函数f: X -->X,定理表明存在一个唯一的函数F:N-->X(N表示包括0的自然数集合),使得满足F(0)=a , F(n+1)=f(F(n)) (对于任何自然数n)。

    唯一性的证明

    取两个函数F:N-->X和G:N-->X使得满足:

    F(0)=a

    G(0)=a

    F(n+1)=f(F(n))

    G(n+1)=f(G(n))

    其中a是集合X中的一个元素。

    数学归纳法可以证明对于所有自然数都有F(n)=G(n):

    基线条件:当n=0时,等式F(0)=a=G(0)成立;

    递归步骤:假设当k∈N时,F(k)=G(K)成立,然后F(k+1)=f(F(k))=f(G(k))=G(k+1),因此F(k)=G(k)意味着F(k+1)=G(k+1)

    通过归纳,F(n)=G(n) (其中n∈N)。

    在计算机科学中

    一种常见的简化方法是将一个问题分成相同类型的子问题。作为一种计算机编程技术,这被称为分治法,是许多重要算法设计的关键。分治法是一种自上而下解决问题的方法,通过解决越来越小的实例来解决问题。相反的方法是动态编程,这种方法是自下而上的方法,通过解决越来越大的实例来解决问题,直到达到所需的大小。

    递归的一个经典例子是阶乘函数的定义,这里用C代码给出:

    unsigned int factorial(unsigned int n) {

    if (n == 0) {

    return 1;

    } else {

    return n * factorial(n - 1);

    }

    }

    该函数在输入的较小版本(n-1)上递归调用自身,并将递归调用的结果乘以n,直到达到基线条件,类似于阶乘的数学定义。

    当一个函数被定义为更简单、通常更小的自身时,计算机编程中的递归就是一个例子。然后通过组合从问题的简单版本中获得的解决方案来设计问题的解决方案。递归的一个示例应用是在编程语言的解析器中。递归的最大优点是通过有限的计算机程序可以定义、解析或产生无限组可能的句子、设计或其他数据。

    递推关系是递归定义一个或多个序列的方程,可以“解决”某些特定类型的递推关系来获得非递归定义。

    在艺术领域

    6d315ab7f3bab391aa506f737bcedacf.png

    602a8fa8cee9c45b1d166fdf8985f06e.png

    俄罗斯娃娃或俄罗斯套娃是递归概念的一个物理艺术例子。

    自1320年乔托的Stefaneschi三联画问世以来,递归就一直用于绘画。它的中央面板包含红衣主教Stefaneschi的跪像,举着三联画本身作为祭品。

    M.C. Eschers 印刷画廊 (1956)描绘了一个扭曲的城市,其中包含一个递归包含图片的画廊,因此无限。

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

    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,就可以通过栈的机制来获得参数。

    展开全文
  • 递归函数的正确思维方法

    万次阅读 多人点赞 2018-02-01 20:40:59
    简单的定义: “当函数直接或者间接调用自己时,则发生了递归.” 说起来简单, 但是理解起来复杂, 因为递归直观, 也符合我们的思维习惯, 相对于递归, 我们更加容易理解迭代. 因为我们日常生活中的思维方式就是...


    什么是递归

    简单的定义: “当函数直接或者间接调用自己时,则发生了递归.” 说起来简单, 但是理解起来复杂, 因为递归并不直观, 也不符合我们的思维习惯, 相对于递归, 我们更加容易理解迭代. 因为我们日常生活中的思维方式就是一步接一步的, 并且能够理解一件事情做了N遍这个概念. 而我们日常生活中几乎不会有递归思维的出现.
    举个简单的例子, 即在C/C++中计算一个字符串的长度. 下面是传统的方式, 我们一般都这样通过迭代来计算长度, 也很好理解.

    size_t length(const char *str) {
      size_t length = 0;
      while (*str != 0) {
        ++length;
        ++str;
      }
    
      return length;
    }
    

    而事实上, 我们也可以通过递归来完成这样的任务.

    size_t length(const char *str) {
      if (*str == 0) {
        return 0;
      }
      return length(++str) + 1;
    }
    

    只不过, 我们都不这么做罢了, 虽然这样的实现有的时候可能代码更短, 但是很明显, 从思维上来说更加难以理解一些. 当然, 我是说假如你不是习惯于函数式语言的话. 这个例子相对简单, 稍微看一下还是能明白吧.
    迭代的算法可以这样描述: 从第一个字符开始判断字符串的每一个字符, 当该字符不为0的时候, 该字符串的长度加一.
    递归的算法可以这样描述: 当前字符串的长度等于当前字符串除了首字符后, 剩下的字符串长度+1.
    作为这么简单的例子, 两种算法其实大同小异, 虽然我们习惯迭代, 但是, 也能看到, 递归的算法无论是从描述上还是实际实现上, 并不比迭代要麻烦.

    理解递归

    在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的回溯验证之中, 因为回溯就像反过来思考迭代, 这是我们习惯的思维方式, 但是实际上递归不需要这样来验证. 比如, 另外一个常见的例子是阶乘的计算. 阶乘的定义: “一个正整数的阶乘(英语:factorial)是所有小于或等于该数的正整数的积,并且0的阶乘为1。” 以下是Ruby的实现:

    def factorial(n) 
      if n <= 1 then
        return 1
      else
        return n * factorial(n - 1)
      end
    end
    

    我们怎么判断这个阶乘的递归计算是否是正确的呢? 先别说测试, 我说我们读代码的时候怎么判断呢?
    回溯的思考方式是这么验证的, 比如当n = 4时, 那么factoria(4)等于4 * factoria(3), 而factoria(3)等于3 * factoria(2)factoria(2)等于2 * factoria(1), 等于2 * 1, 所以factoria(4)等于4 * 3 * 2 * 1. 这个结果正好等于阶乘4的迭代定义.
    用回溯的方式思考虽然可以验证当n = 某个较小数值是否正确, 但是其实无益于理解.
    Paul Graham提到一种方法, 给我很大启发, 该方法如下:

    1. 当n=0, 1的时候, 结果正确.
    2. 假设函数对于n是正确的, 函数对n+1结果也正确.
      如果这两点是成立的,我们知道这个函数对于所有可能的n都是正确的。

    这种方法很像数学归纳法, 也是递归正确的思考方式, 事实上, 阶乘的递归表达方式就是1!=1,n!=(n-1)!×n(见wiki). 当程序实现符合算法描述的时候, 程序自然对了, 假如还不对, 那是算法本身错了…… 相对来说, n,n+1的情况为通用情况, 虽然比较复杂, 但是还能理解, 最重要的, 也是最容易被新手忽略的问题在于第1点, 也就是基本用例(base case)要对. 比如, 上例中, 我们去掉if n <= 1的判断后, 代码会进入死循环, 永远不会结束.

    使用递归

    既然递归比迭代要难以理解, 为啥我们还需要递归呢? 从上面的例子来看, 自然意义不大, 但是很多东西的确用递归思维会更加简单……
    经典的例子就是斐波那契数列, 在数学上, 斐波那契数列就是用递归来定义的:

    ·F0 = 0
    ·F1 = 1 
    ·Fn = Fn – 1 + Fn – 2

    有了递归的算法, 用程序实现实在再简单不过了:

    def fibonacci(n)
      if n == 0 then
        return 0
      elsif n == 1 then
        return 1
      else
        return fibonacci(n - 1) + fibonacci(n - 2)
      end
    end
    

    改为用迭代实现呢? 你可以试试.
    上面讲了怎么理解递归是正确的, 同时可以看到在有递归算法描述后, 其实程序很容易写, 那么最关键的问题就是, 我们怎么找到一个问题的递归算法呢?
    Paul Graham提到, 你只需要做两件事情:

    1. 你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.
    2. 你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).
      如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决.

    这个过程还是数学归纳法的方法, 只不过和上面提到的一个是验证, 一个是证明.
    现在我们用这个方法来寻找汉诺塔这个游戏的解决方法.(这其实是数学家发明的游戏)

    有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
    1.每次只能移动一个圆盘.
    2.大盘不能叠在小盘上面.

    汉诺塔

    这个游戏在只有3个盘的时候玩起来较为简单, 盘越多, 就越难, 玩进去后, 你就会进入一种不停的通过回溯来推导下一步该干什么的状态, 这是比较难的. 我记得第一次碰到这个游戏好像是在大航海时代某一代游戏里面, 当时就觉得挺有意思的. 推荐大家都实际的玩一下这个游戏, 试试你脑袋能想清楚几个盘的情况.
    现在我们来应用Paul Graham的方法思考这个游戏.

    一般情况:
    当有N个圆盘在A上, 我们已经找到办法将其移到C杠上了, 我们怎么移动N+1个圆盘到C杠上呢? 很简单, 我们首先用将N个圆盘移动到C上的方法将N个圆盘都移动到B上, 然后再把第N+1个圆盘(最后一个)移动到C上, 再用同样的方法将在B杠上的N个圆盘移动到C上. 问题解决.

    基本用例:
    当有1个圆盘在A上, 我们直接把圆盘移动到C上即可.

    算法描述大概就是上面这样了, 其实也可以看作思维的过程, 相对来说还是比较自然的. 下面是Ruby解:

    def hanoi(n, from, to, other)
      if n == 1 then
        puts from + ' -> ' + to
      else
        hanoi(n-1, from, other, to)
        hanoi(1, from, to, other)
        hanoi(n-1, other, to, from)
      end
    end
    

    当n=3时的输出:

    A -> C
    A -> B
    C -> B
    A -> C
    B -> A
    B -> C
    A -> C

    上述代码中, from, to, other的作用其实也就是提供一个杆子的替代符, 在n=1时, 其实也就相当于直接移动. 看起来这么复杂的问题, 其实用递归这么容易, 没有想到吧. 要是想用迭代来解决这个问题呢? 还是你自己试试吧, 你试的越多, 就能越体会到递归的好处.

    递归的问题

    当然, 这个世界上没有啥时万能的, 递归也不例外, 首先递归并不一定适用所有情况, 很多情况用迭代远远比用递归好了解, 其次, 相对来说, 递归的效率往往要低于迭代的实现, 同时, 内存好用也会更大, 虽然这个时候可以用尾递归来优化, 但是尾递归并不是一定能简单做到.

    展开全文
  • 递归

    2016-08-15 12:12:12
    递归概念:  递归算法是一种直接或者间接调用自身函数或者方法的算法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。 使用递归的两个条件: 既然递归的思想是把问题分解成为规模...

    递归概念

     递归算法是一种直接或者间接调用自身函数或者方法的算法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

    使用递归的两个条件

    既然递归的思想是把问题分解成为规模更小且与原问题有着相同解法的问题,那么是不是这样的问题都能用递归来解决呢?答案是否定的。并不是所有问题都能用递归来解决。那么什么样的问题可以用递归来解决呢?一般来讲,能用递归来解决的问题必须满足两个条件:

    1. 可以通过递归调用来缩小问题规模,且新问题与原问题有着相同的形式。
    2. 存在一种简单情境,可以使递归在简单情境下退出
    例如,求斐波那契数列的第N项的值?

    斐波那契数列这样定义:f(0) = 0, f(1) = 1, 对n > 1, f(n) = f(n-1) + f(n-2)。这是一个明显的可以用递归解决的问题。让我们来看看它是如何满足递归的两个条件的:

    1. 对于一个n>2, 求f(n)只需求出f(n-1)和f(n-2),也就是说规模为n的问题,转化成了规模更小的问题;
    2. 对于n=0和n=1,存在着简单情境:f(0) = 0, f(1) = 1。
    计算费波纳契数列的第n项的递归程序:

    int fib(n)
    {
        if(n == 0)
            return 0;
        else if(n == 1)
            return 1;
        else
            return f(n-1) + f(n-2);
    }
    递归算法与循环算法对比(参考漫谈递归:递归与循环

    1. 递归算法:

    • 优点:代码简洁、清晰,并且容易验证正确性。(如果你真的理解了算法的话,否则你更晕)
    • 缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理(还有可能出现堆栈溢出的情况),比如参数传递需要压栈等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,那将是极端难看的代码。

    2. 循环算法:

    • 优点:速度快,结构简单。
    • 缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。

    3. 递归算法和循环算法总结:

    递归通常很直白地描述了一个求解过程,因此也是最容易被想到和实现的算法。循环其实和递归具有相同的特性(即:做重复任务),但有时,使用循环的算法并不会那么清晰地描述解决问题步骤。单从算法设计上看,递归和循环并无优劣之别。然而,在实际开发中,因为函数调用的开销,递归常常会带来性能问题,特别是在求解规模不确定的情况下。而循环因为没有函数调用开销,所以效率会比递归高。除少数编程语言对递归进行了优化外,大部分语言在实现递归算法时还是十分笨拙,由此带来了如何将递归算法转换为循环算法的问题。算法转换应当建立在对求解过程充分理解的基础上,有时甚至需要另辟蹊径。

    • 一般递归调用可以处理的算法,也通过循环去解决需要额外的低效处理。
    • 现在的编译器在优化后,对于多次调用的函数处理会有非常好的效率优化,效率未必低于循环。
    • 递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换,而不影响程序的阅读,那么替换成递归往往是好的。(例如:求阶乘的递归实现与循环实现。)

    归纳法理解递归:

    递归的数学模型其实就是归纳法,

    归纳法适用于想解决一个问题转化为解决他的子问题,而他的子问题又变成子问题的子问题,而且我们发现这些问题其实都是一个模型,也就是说存在相同的逻辑归纳处理项。当然有一个是例外的,也就是递归结束的哪一个处理方法不适用于我们的归纳处理项,当然也不能适用,否则我们就无穷递归了。这里又引出了一个归纳终点以及直接求解的表达式。如果运用列表来形容归纳法就是:

    • 步进表达式:问题蜕变成子问题的表达式
    • 结束条件:什么时候可以不再是用步进表达式
    • 直接求解表达式:在结束条件下能够直接计算返回值的表达式
    • 逻辑归纳项:适用于一切非适用于结束条件的子问题的处理,当然上面的步进表达式其实就是包含在这里面了。
    即递归的一般形式:

    void func( mode)
    {
        if(endCondition)
        {
            constExpression         //基本项
        }
        else
        {
            accumrateExpreesion     //归纳项
            mode=expression         //步进表达式
            func(mode)          //调用本身,递归
        }
    }
    
    :在编写递归调用的函数的时候,一定要把对简单情境的判断写在最前面,以保证函数调用在检查到简单情境的时候能够及时地中止递归,否则,你的函数可能会永不停息的在那里递归调用了


    递归的一些应用:递归算法实例讲解

    • 斐波纳契数列(Fibonacci Sequence)
    • n的阶乘
    • 汉诺塔问题

    参考:


    展开全文
  • 这是磊哥的第 189 期分享作者 | 田小齐来源 | 码农田小齐(ID:NYCSDE)分享| Java中文社群(ID:javacn666)前言 递归,是一个非常重要的概念,也是面试中...
  • 递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对时间空间复杂度的理解和分析。 本文只讲一题,也是几乎所有算法书讲递归的第一题,但力争讲出花来,...
  • 我想,没有比下面这个例子更能形象简单的描述递归啦!请大家看下面这个在数学里常见的函数: 这是一个函数的常见表达形式,他代表着1、2、3、4、……、n-1、n这个数列。通常我们想求得除了n=1以外的任意一...
  • 递归是一种抽象的概念,比如当我们想要完成某一递归函数DFS()的功能时,你可以先假设这个DFS()已经有你想要的功能啦,之后再书写边界条件,然后再书写具体功能的实现,关注过程,只关注结果,当然前提在有点思路的情况下 ...
  • 递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对时间空间复杂度的理解和分析。 本文只讲一题,也是几乎所有算法书讲递归的第一题,但力争讲出花来,...
  • 递归是编程中一个相对难以理解但是却又很重要的概念. 对于从命令式语言开始学习编程的程序员天生对此有理解缺陷, 而对于从类似C++这种对函数式编程范式友好的语言开始学习编程的程序员就更加如此了.(比如我自己) ...
  • 轻轻松松学递归

    千次阅读 多人点赞 2019-09-05 12:54:33
    一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算...
  • 很多时候我们看明白一个复杂的递归都有点费时间,尤其对模型所描述的问题概念不清的时候,想要自己设计一个递归那么就更是有难度了。很多理解递归的人(今天在csdn里面看到一个初学者的留言),总认为递归完全没必要...
  • 版权声明:本作品由九天雁翎创作,采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。... 递归是编程中一个相对难以理解但是却又很重要...
  • 漫谈递归

    2016-08-04 15:44:57
    漫谈递归
  • 在此对于一些常用算法思想做一个概念上的简单总结 1、递归的基本概念 一般来说,递归是一个过程或函数在它的定义或说明中又直接或间接调用它自己的一种方法。...递归只需少量的程序就可描述出...
  • 很多时候我们看明白一个复杂的递归都有点费时间,尤其对模型所描述的问题概念不清的时候,想要自己设计一个递归那么就更是有难度了。 很多理解递归的人(今天在csdn里面看到一个初学者的留言),总认为递
  • 递归入门

    2017-10-25 21:11:22
    写在前面: 对于强大的递归。要想做到灵活运用,是需要花时间进行练习并总结。往往递归学习的入门也是难度也比较大,常常...在此推荐一本学习递归较好的的入门书:《程序设计抽象思想:C语言描述》 。本文章也引用
  • 很多时候我们看明白一个复杂的递归都有点费时间,尤其对模型所描述的问题概念不清的时候,想要自己设计一个递归那么就更是有难度了。 很多理解递归的人(今天在csdn里面看到一个初学者的留言),总认为递归完全...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,352
精华内容 18,540
关键字:

关于递归概念描述不正确的是