精华内容
下载资源
问答
  • 递归算法时间复杂度分析

    万次阅读 多人点赞 2018-09-17 16:16:59
    递归算法时间复杂度分析 时间复杂度: 一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。 T...

                                 递归算法时间复杂度分析

    时间复杂度: 

    一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。 
    T(n)=o(f(n)); 
    它表示随问题规模n的增大,算法的执行时间增长率和f(n)增长率成正比,这称作算法的渐进时间复杂度。而我们一般情况下讨论的最坏的时间复杂度。 
    空间复杂度: 
    算法的空间复杂度并不是实际占用的空间,而是计算整个算法空间辅助空间单元的个数,与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。 
    S(n)=o(f(n)) 
    若算法执行所需要的辅助空间相对于输入数据n而言是一个常数,则称这个算法空间复杂度辅助空间为o(1); 
    递归算法空间复杂度:递归深度n*每次递归所要的辅助空间,如果每次递归所需要的辅助空间为常数,则递归空间复杂度o(n)。

    递归算法分析

    1、利用数列知识

    1. 累加法:递推关系式为an+1−an=f(n)an+1−an=f(n)采用累加法。
    2. 累乘法:递推关系式为an+1an=f(n)an+1an=f(n)采用累乘法。
    3. 构造法:递推关系式为(1)aa+1=pan+qaa+1=pan+q,(2)aa+1=pan+qnaa+1=pan+qn,都可以通过恒等变形,构造出等差或等比数列,利用等差或等比数列的定义进行解题,其中的构造方法可通过待定系数法来进行。
    4. 和化项法:递推公式为Sn=f(n)Sn=f(n)或Sn=f(an)Sn=f(an)一般利用

      an={S1,Sn−Sn−1,当n=1当n>=2an={S1,当n=1Sn−Sn−1,当n>=2

    5. 用特征方程求解递推方程(感觉比较生僻,不做解释)
    6. 迭代法: 从原始递推方程开始,反复将对于递推方程左边的函数用右边的等式代入,直到得到初值,然后将所得的结果进行化简。 
      例如在调用归并排序mergeSort(a,0,n-1)对数组a[0...n−1]a[0...n−1]排序时,执行时间T(n)T(n)的递推关系式为:

      T(n)={O(1),2T(n2)+O(n),当n=1当n>=2T(n)={O(1),当n=12T(n2)+O(n),当n>=2


      其中,O(n)O(n)为merge()所需要的时间,设为cncn(c为正常量)。因此: 

      T(n)=2T(n2)+cn=2(2T(n4)+cn2)+cn=22T(n4)+2cn=23T(n8)+3cn=...=2kT(n2k)+kcn=nO(1)+cnlog2n=O(nlog2n),(假设n=2k,则k=log2n)T(n)=2T(n2)+cn=2(2T(n4)+cn2)+cn=22T(n4)+2cn=23T(n8)+3cn=...=2kT(n2k)+kcn=nO(1)+cnlog2⁡n=O(nlog2⁡n),(假设n=2k,则k=log2⁡n)


      忽略求解细节。在我们求解递归式时,因为最终是要求得一个时间上限,所以在求解时常常省略一些细节。比如mergeSort(a,0,n-1)运行时间的实际递归式应该是: 

    T(n)={O(1),T(⌈n2⌉)+T(⌊n2⌋)+O(n),当n=1当n>=2T(n)={O(1),当n=1T(⌈n2⌉)+T(⌊n2⌋)+O(n),当n>=2


    但我们忽略这些上取整、下取整以及边界条件,甚至假设问题规模n=2kn=2k,这都是为方便求解而忽略的细节。经验和一些定理告诉我们,这些细节不会影响算法时间复杂度的渐近界。

     

      类似的,我们也可以用迭代法求解汉诺塔递归求解时的时间复杂度。但遗憾的是,迭代法一般适用于一阶的递推方程。对于二阶及以上(即T(n)依赖它前面更多个递归项T(n)依赖它前面更多个递归项)的递推方程,迭代法将导致迭代后的项太多,从而使得求和公式过于复杂,因此需要将递推方程化简,利用差消法等技巧将高阶递推方程化为一阶递推方程。如在求快速排序算法平均时间复杂度T(n)T(n)的递推方程,T(n)T(n)依赖T(n−1)、T(n−2)、...、T(1)T(n−1)、T(n−2)、...、T(1)等所有的项,这样的递推方程也称为全部历史递推方程。(这里省略快速排序算法平均复杂度T(n)的求解过程)

    小结:上面6种递推关系是高中、本科知识,在此重点介绍了迭代法,其它几种方法虽未在本篇中使用,但可以加深对递推式求解的认识。


    2、代入法

    代入法实质上就是数学归纳法,因此求递推式分为两步:

    1. 猜测解的形式;
    2. 用数学归纳法求出解中的常数,并证明解是正确的。

      遗憾的是并不存在通用的方法来猜测递归式的正确解,需要凭借经验,偶尔还需要创造力。即使猜出了递归式解的渐近界,也有可能在数学归纳证明时莫名其妙的失败。正是由于该方法技术细节较为难掌握,因此这个方法不适合用来求解递归方程,反而比较适合作为其他方法检验手段。在此不做总结。可以翻阅《算法导论》进行学习。


    3、递归树

      递归树是一棵结点带权值的树。初始的递归树只有一个结点,它的权标记为T(n)T(n);然后按照递归树的迭代规则不断进行迭代,每迭代一次递归树就增加一层,直到树中不再含有权值为函数的结点(即叶结点都为T(1)T(1))。下面以递归方程

    T(n)={O(1),2T(n2)+O(n),当n=1当n>=2;(假设n=2k,则k=log2n)T(n)={O(1),当n=12T(n2)+O(n),当n>=2;(假设n=2k,则k=log2⁡n)

    来讲述递归树的迭代规则。

     

    • 第一步: 把根结点T(n)T(n)用根是cncn、左结点为T(n2)T(n2)、右结点为T(n2)T(n2)的子树代替(即:以分解、合并子问题需要的代价为根,分解得到的子问题为叶的子树。其中常量c代表求解规模为1的问题所需的时间);(如下如(a)→(b)(a)→(b))
    • 第二步:把叶结点按照“第一步”的方式展开;T(n2)T(n2)用根是cn/2cn/2、左节点为T(n4)T(n4)、右结点为T(n4)T(n4)的子树代替。(如下如(b)→(c)(b)→(c))
    • 第三步:反复按照“第一步”的方式迭代,每迭代一次递归树就增加一层,直到树中不再含有权值为函数的结点(即叶结点都为T(1)T(1))。(如下如(c)→(d)(c)→(d))

     

    这里写图片描述

     

      在得到递归树后,将树中每层中的代价求和,得到每层代价,然后将所有层的代价求和,得到所有层次的递归调用的总代价。在上图(d)部分中,完全展开的递归树高度为lgnlg⁡n(树高为根结点到叶结点最长简单路径上边的数目),所有递归树具有lgn+1lg⁡n+1层,所以总代价为cn∗(lgn+1)cn∗(lg⁡n+1),所有时间复杂度为Θ(nlgn)Θ(nlg⁡n)。

      总结:递归树模型求解递归方程,本质上就是迭代思想的应用,利用递归方程迭代展开过程构造对应的递归树,然后把每层的时间代价进行求和。不过递归树模型更直观,同时递归树也克服了二阶及更高阶递推方程不方便迭代展开的痛点。


    4、主方法求解递推式

      主方法为如下形式的递归式提供了一种“菜谱”式的求解方法,如下所示 

    T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)

     

    其中a≥1a≥1和b>1b>1是常数,f(n)f(n)是渐近正函数。这个递推式将规模为n的问题分解为a个子问题,每个子问题的规模为n/bn/b,a个子问题递归地求解,每个花费时间T(n/b)T(n/b)。函数f(n)f(n)包含了问题分解和子问题解合并的代价。同样,这个递归式也没有考虑上取整、下取整、边界条件等,结果不会影响递归式的渐近性质。

    定理4.1(主定理) 令a≥1和b>1是常数,f(n)f(n)是一个函数,T(n)T(n)是定义在非负整数上的递归式: 

    T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)


    其中我们将n/bn/b解释为⌊n/b⌋⌊n/b⌋或⌈n/b⌉⌈n/b⌉。那么T(n)T(n)有如下渐近界: 
    1. 若对某个常数ε>0ε>0有f(n)=O(n(logba)−ε)f(n)=O(n(logb⁡a)−ε),则T(n)=Θ(nlogba)T(n)=Θ(nlogb⁡a) 
    2. 若f(n)=Θ(nlogba)f(n)=Θ(nlogb⁡a),则T(n)=Θ(nlogbalgn)T(n)=Θ(nlogb⁡alg⁡n)。 
    3. 若对某个常数ε>0ε>0有f(n)=Ω(n(logba)+ε)f(n)=Ω(n(logb⁡a)+ε),且对某个常数c<1c<1和所有足够大的n有af(n/b)≤cf(n)af(n/b)≤cf(n),则T(n)=Θ(f(n))T(n)=Θ(f(n))

     

      在使用主定理之前,要比较f(n)和(nlogba)f(n)和(nlogb⁡a)的大小,这个大小不是算术意义上的大小比较,而是要在多项式意义上比较。以上三种情况在多项式意义上并未覆盖f(n)f(n)的所有可能性。情况1和情况2之间有一定间隙;情况2和情况3之间也有一定间隙。如果f(n)落在这两个间隙中,或者情况3中 正则条件不成立,就不能使用主方法来求递归式。 
      如在递归式:T(n)=2T(n/2)+nlgnT(n)=2T(n/2)+nlg⁡n中,因为 nlogba=n<f(n)=nlgnnlogb⁡a=n<f(n)=nlg⁡n,但是f(n)f(n)并不大于n一个多项式因子nεnε ,因为对于给定的ε>0ε>0当n足够大时,均有nε>lgnnε>lg⁡n。所以找不到这样 ε>0ε>0,该递归式落入了情况2和情况3之间的间隙,不能使用主定理。 
      最后给出主定理应用的几个练习题:

     

    主方法联系

    具体举例分析:

    【代入法】代入法首先要对这个问题的时间复杂度做出预测,然后将预测带入原来的递归方程,如果没有出现矛盾,则是可能的解,最后用数学归纳法证明。

      【举   例】我们有如下的递归问题:T(n)=4T(n/2)+O(n),我们首先预测时间复杂度为O(n2),不妨设T(n)=kn2(其中k为常数),将该结果带入方程中可得:左=kn2,右=4k(n/2)2+O(n)=kn2+O(n),由于n2的阶高于n的阶,因而左右两边是相等的,接下来用数学归纳法进行验证即可。


       【迭代法】迭代法就是迭代的展开方程的右边,直到没有可以迭代的项为止,这时通过对右边的和进行估算来估计方程的解。比较适用于分治问题的求解,为方便讨论起见,给出其递归方程的一般形式:

      【举   例】下面我们以一个简单的例子来说明:T(n)=2T(n/2)+n2,迭代过程如下:

      容易知道,直到n/2^(i+1)=1时,递归过程结束,这时我们计算如下:

      到这里我们知道该算法的时间复杂度为O(n2),上面的计算中,我们可以直接使用无穷等比数列的公式,不用考虑项数i的约束,实际上这两种方法计算的结果是完全等价的,有兴趣的同学可以自行验证。


    【公式法】这个方法针对形如:T(n) = aT(n/b) + f(n)的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系,即一个规模为n的问题被分成规模均为n/b的a个子问题,递归地求解这a个子问题,然后通过对这a个子问题的解的综合,得到原问题的解。这种方法是对于分治问题最好的解法,我们先给出如下的公式:

      公式记忆:我们实际上是比较n^logba和f(n)的阶,如果他们不等,那么T(n)取他们中的较大者,如果他们的阶相等,那么我们就将他们的任意一个乘以logn就可以了。按照这个公式,我们可以计算【迭代法】中提到的例子:O(f(n))=O(n2),容易计算另外一个的阶是O(n),他们不等,所以取较大的阶O(n2)。太简单了,不是吗?

      需要注意:上面的公式并不包含所有的情况,比如第一种和第二种情况之间并不包含下面这种情况:f(n)是小于前者,但是并不是多项式的小于前者。同样后两种的情况也并不包含所有的情况。为了好理解与运用的情况下,笔者将公式表述成如上的情况,但是并不是很严谨,关于该公式的严密讨论,请看这里。但是公式的不包含的情况,我们很少很少碰到,上面的公式适用范围很广泛的。

      特别地,对于我们经常碰到的,当f(n)=0时,我们有:


    【母函数法】母函数是用于对应于一个无穷序列的幂级数。这里我们解决的递归问题是形如:T(n)=c1T(n-1)+c2T(n-2)+c3T(n-3)+...+ckT(n-k)+f(n)。为说明问题简便起见,我们选择斐波那契数列的时间复杂度作为例子进行讨论。

      【举  例】斐波那契数列递归公式:T(n)=T(n-1)+T(n-2)。这里我们假设F(n)为第n项的运算量。则容易得到:F(n)=F(n-1)+F(n-2),其中F(1)=F(2)=1.我们构造如下的母函数:G(x)=F(1)x+F(2)x2+F(3)x3+......,我们可以推导如下:

      上面的方法计算相对来说是比较简单的,关键在于对于母函数的理解,刚开始的时候可能不是很好理解,对于母函数可以参考这里维基百科这里


    【差分方程法】可以将某些递归方程看成差分方程,通过解差分方程的方法来解递归方程,然后对解作出渐近阶估计。这里我们只考虑最长常见的递归形式,形如:T(n)=c1T(n-1)+c2T(n-2)+c3T(n-3)+...+ckT(n-k)+f(n),其中c1,c2,...ck为常数且不等于0;我们对该方程的求解如下:

      对应上面的齐次方程的特征方程为:

      如果解得t=r是该特征方程的m重根,则这m个解的形式为:{rn     n*rn      n2rn   ...    nm-1rn},其余的关于复数解的形式和普通的线性方程组的形式类似,不再赘述。接下来,我们要求解该方程的对应非齐次方程组的通解,这里我们针对该方程的特殊形式,不加证明地给出如下的通解形式:

      则和线性代数中的解一样,原方程的解等于齐次方程组的通解+特解,即:

      最后由初始条件确定a(i)的值即可。

      为了帮助理解,我们举两个例子看看,就明白是怎么回事了。

      【举 例1】递归方程如下:

    (1)写出对应齐次方程的特征方程:

    得到基础解系为:{t1n,  t2n}

    (2)计算特解,对于本题,直接观察得特解为:-8

    (3)得到原方程解的形式为:T(n)=a0t1n+a1t2n-8

    (4)代入n=0,n=1的情况,得到a0,a1,最后可得:

      可以看到该方程形式和上面讨论过的斐波那契数列只差一个常数8,因而两者的时间复杂度是相同的。有兴趣的同学可以按照这个方法再次计算斐波那契数列的时间复杂度验证一下。

      【举  例2】递归方程如下:

    (1)计算对应齐次方程的基础解析:特征方程为:C(t)=t^2-4t-4=0,得到一个2重根t=2.因而其基础解为:{2n      n*2n}

    (2)由于f(n)=n*2n,对应上面表格的最后一种情况,得到特解形式为:T(n)=n2(p0+p1n)2n代入原递归方程可得:p0=1/2,p1=1/6

    (3)原方程解的形式为:T(n)=a0*2n+a1*n*2n+n2(1/2+n/6)2n,代入T(0),T(1)得:a0=a1=0

    (4)综上:T(n)=n2(1/2+n/6)2n

    因而时间复杂度为:O(n32n).

     

    参考:https://blog.csdn.net/so_geili/article/details/53444816

              https://blog.csdn.net/m0_37734999/article/details/78751882

              https://www.cnblogs.com/hlongch/p/5749038.html

    展开全文
  • 递归算法详解

    千次阅读 2016-05-15 09:18:13
    转载自:ShinChan’s Blog 计算机科学的新学生通常难以理解递归程序设计的概念。递归思想之所以困难,原因在于它非常像是循环推理(circular ...递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归

    转载自:ShinChan’s Blog

      计算机科学的新学生通常难以理解递归程序设计的概念。递归思想之所以困难,原因在于它非常像是循环推理(circular reasoning)。它也不是一个直观的过程;当我们指挥别人做事的时候,我们极少会递归地指挥他们。

    Introduction

      递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解。递归算法,其实说白了,就是程序的自身调用。它表现在一段程序中往往会遇到调用自身的那样一种coding策略,这样我们就可以利用大道至简的思想,把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。递归往往能给我们带来非常简洁非常直观的代码形势,从而使我们的编码大大简化,然而递归的思维确实很我们的常规思维相逆的,我们通常都是从上而下的思维问题, 而递归趋势从下往上的进行思维。这样我们就能看到我们会用很少的语句解决了非常大的问题,所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。
      递归算法解决问题的特点:

    递归就是方法里调用自身。
    在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。
    递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
    在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等,所以一般不提倡用递归算法设计程序。
      递归算法要求。递归算法所体现的“重复”一般有三个要求:

      (1) 是每次调用在规模上都有所缩小(通常是减半);
      (2) 是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入);
      (3) 是在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。

    从递归的经典示例开始

      计算阶乘是递归程序设计的一个经典示例。计算某个数的阶乘就是用那个数去乘包括 1 在内的所有比它小的数。例如,factorial(5) 等价于 5*4*3*2*1,而 factorial(3) 等价于 3*2*1。
      阶乘的一个有趣特性是,某个数的阶乘等于起始数(starting number)乘以比它小一的数的阶乘。例如,factorial(5) 与 5 * factorial(4) 相同。您很可能会像这样编写阶乘函数:

     factorial( n){
        return n * factorial(n - );

    (注:本文的程序示例用C语言编写)
      不过,这个函数的问题是,它会永远运行下去,因为它没有终止的地方。函数会连续不断地调用 factorial。 当计算到零时,没有条件来停止它,所以它会继续调用零和负数的阶乘。因此,我们的函数需要一个条件,告诉它何时停止。
      由于小于 1 的数的阶乘没有任何意义,所以我们在计算到数字 1 的时候停止,并返回 1 的阶乘(即 1)。因此,真正的递归函数类似于:

     factorial( n){
        (n == )
            return ;
          return n * factorial(n - );

      可见,只要初始值大于零,这个函数就能够终止。停止的位置称为 基线条件(base case)。基线条件是递归程序的 最底层位置,在此位置时没有必要再进行操作,可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件,而且 必须确保它们最终会达到某个基线条件;否则,程序将永远运行下去,直到程序缺少内存或者栈空间。

    斐波纳契数列

      斐波纳契数列(Fibonacci Sequence),最开始用于描述兔子生长的数目时用上了这数列。从数学上,费波那契数列是以递归的方法来定义:

    这样斐波纳契数列的递归程序就可以非常清晰的写出来了:

     Fibonacci( n){
         (n <= )  
            return n;  
            return Fibonacci(n-) + Fibonacci(n-);  

    递归程序的基本步骤

      每一个递归程序都遵循相同的基本步骤:

    () 初始化算法。递归程序通常需要一个开始时使用的种子值(seed value)。要完成此任务,可以向函数传递参数,或者提供一个入口函数, 这个函数是非递归的,但可以为递归计算设置种子值。
    () 检查要处理的当前值是否已经与基线条件相匹配。如果匹配,则进行处理并返回值。
    () 使用更小的或更简单的子问题(或多个子问题)来重新定义答案。
    () 对子问题运行算法。
    () 将结果合并入答案的表达式。
    () 返回结果。
    使用归纳定义

      有时候,编写递归程序时难以获得更简单的子问题。 不过,使用 归纳定义的(inductively-defined)数据集 可以令子问题的获得更为简单。归纳定义的数据集是根据自身定义的数据结构 —— 这叫做 归纳定义(inductive definition)。
      例如,链表就是根据其本身定义出来的。链表所包含的节点结构体由两部分构成:它所持有的数据,以及指向另一个节点结构体(或者是 NULL,结束链表)的指针。 由于节点结构体内部包含有一个指向节点结构体的指针,所以称之为是归纳定义的。
      使用归纳数据编写递归过程非常简单。注意,与我们的递归程序非常类似,链表的定义也包括一个基线条件 —— 在这里是 NULL 指针。 由于 NULL 指针会结束一个链表,所以我们也可以使用 NULL 指针条件作为基于链表的很多递归程序的基线条件。
      下面看两个例子。

    链表求和示例

      让我们来看一些基于链表的递归函数示例。假定我们有一个数字列表,并且要将它们加起来。履行递归过程序列的每一个步骤,以确定它如何应用于我们的求和函数:

    () 初始化算法。这个算法的种子值是要处理的第一个节点,将它作为参数传递给函数。
    () 检查基线条件。程序需要检查确认当前节点是否为 列表。如果是,则返回零,因为一个空列表的所有成员的和为零。
    () 使用更简单的子问题重新定义答案。我们可以将答案定义为当前节点的内容加上列表中其余部分的和。为了确定列表其余部分的和, 我们针对下一个节点来调用这个函数。
    () 合并结果。递归调用之后,我们将当前节点的值加到递归调用的结果上。
      这样我们就可以很简单的写出链表求和的递归程序,实例如下:

    sum_list(struct list_node *l){
        (l == NULL)
            return ;
        return l.data + sum_list(l.next);

    汉诺塔问题

      汉诺塔(Hanoi Tower)问题也是一个经典的递归问题,该问题描述如下:

    汉诺塔问题:古代有一个梵塔,塔内有三个座、B、C,座上有个盘子,盘子大小不等,大的在下,小的在上(如图)。有一个和尚想把这个盘子从座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,个座上的盘子始终保持大盘在下,小盘在上。
      Hanoi Tower
    如果只有 1 个盘子,则不需要利用B塔,直接将盘子从A移动到C。
    如果有 2 个盘子,可以先将盘子1上的盘子2移动到B;将盘子1移动到C;将盘子2移动到C。这说明了:可以借助B将2个盘子从A移动到C,当然,也可以借助C将2个盘子从A移动到B。
    如果有3个盘子,那么根据2个盘子的结论,可以借助c将盘子1上的两个盘子从A移动到B;将盘子1从A移动到C,A变成空座;借助A座,将B上的两个盘子移动到C。
      以此类推,上述的思路可以一直扩展到 n 个盘子的情况,将将较小的 n-1个盘子看做一个整体,也就是我们要求的子问题,以借助B塔为例,可以借助空塔B将盘子A上面的 n-1 个盘子从A移动到B;将A最大的盘子移动到C,A变成空塔;借助空塔A,将B塔上的 n-2 个盘子移动到A,将C最大的盘子移动到C,B变成空塔…
      根据以上的分析,不难写出程序:

     Hanoi ( n,  A,  B,  C){
         (n==){ //end condition
            move(A,B);//‘move’ can be defined to be a print function
            Hanoi(n-,A,C,B);//move sub [n-1] pans from A to B
            move(A,C);//move the bottom(max) pan to C
            Hanoi(n-,B,A,C);//move sub [n-1] pans from B to C

    将循环转化为递归

      在下表中了解循环的特性,看它们可以如何与递归函数的特性相对比。

    PROPERTIES LOOPS RECURSIVE FUNCTIONS
    重复 为了获得结果,反复执行同一代码块;以完成代码块或者执行 continue 命令信号而实现重复执行。 为了获得结果,反复执行同一代码块;以反复调用自己为信号而实现重复执行。
    终止条件 为了确保能够终止,循环必须要有一个或多个能够使其终止的条件,而且必须保证它能在某种情况下满足这些条件的其中之一。 为了确保能够终止,递归函数需要有一个基线条件,令函数停止递归。
    状态 循环进行时更新当前状态。 当前状态作为参数传递。
      可见,递归函数与循环有很多类似之处。实际上,可以认为循环和递归函数是能够相互转换的。 区别在于,使用递归函数极少被迫修改任何一个变量 —— 只需要将新值作为参数传递给下一次函数调用。 这就使得您可以获得避免使用可更新变量的所有益处,同时能够进行重复的、有状态的行为。
      下面还是以阶乘为例子,循环写法为:

     factorial( n){
         product = ;
        while(n>){
            product *= n;
        return product;

      递归写法在第二节中已经介绍过了,这里就不重复了,可以比较一下。

    尾递归介绍

      对于递归函数的使用,人们所关心的一个问题是栈空间的增长。确实,随着被调用次数的增加,某些种类的递归函数会线性地增加栈空间的使用 —— 不过,有一类函数,即尾部递归函数,不管递归有多深,栈的大小都保持不变。尾递归属于线性递归,更准确的说是线性递归的子集。
      函数所做的最后一件事情是一个函数调用(递归的或者非递归的),这被称为 尾部调用(tail-call)。使用尾部调用的递归称为 尾部递归。当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。
      让我们来看一些尾部调用和非尾部调用函数示例,以了解尾部调用的含义到底是什么:

     test1(){
        test1(); /* recursive, but not a tail call.  We continue */
                 /* processing in the function after it returns. */
        a = a + ;
        return a;
     test2(){
        q = q + ;
        return q + test1(); /* test1() is not in tail position.
                             * There is still more work to be
                             * done after test1() returns (like
                             * adding q to the result*/
     test3(){
        b = b + ;
        return test1();  /* This is a tail-call.  The return value
                          * of test1() is used as the return value
                          * for this function.*/                    
     test4(){
        test3(); /* not in tail position */
        test3(); /* not in tail position */
        return test3(); /* in tail position */

      可见,要使调用成为真正的尾部调用,在尾部调用函数返回之前,对其结果 不能执行任何其他操作。
    注意,由于在函数中不再做任何事情,那个函数的实际的栈结构也就不需要了。惟一的问题是,很多程序设计语言和编译器不知道 如何除去没有用的栈结构。如果我们能找到一个除去这些不需要的栈结构的方法,那么我们的尾部递归函数就可以在固定大小的栈中运行。
      在尾部调用之后除去栈结构的方法称为 尾部调用优化 。
      那么这种优化是什么?我们可以通过询问其他问题来回答那个问题:

    (1) 函数在尾部被调用之后,还需要使用哪个本地变量?哪个也不需要。
    (2) 会对返回的值进行什么处理?什么处理也没有。
    (3) 传递到函数的哪个参数将会被使用?哪个都没有。
      好像一旦控制权传递给了尾部调用的函数,栈中就再也没有有用的内容了。虽然还占据着空间,但函数的栈结构此时实际上已经没有用了,因此,尾部调用优化就是要在尾部进行函数调用时使用下一个栈结构 覆盖 当前的栈结构,同时保持原来的返回地址。
      我们所做的本质上是对栈进行处理。再也不需要活动记录(activation record),所以我们将删掉它,并将尾部调用的函数重定向返回到调用我们的函数。 这意味着我们必须手工重新编写栈来仿造一个返回地址,以使得尾部调用的函数能直接返回到调用它的函数。   

    Conclusion

      递归是一门伟大的艺术,使得程序的正确性更容易确认,而不需要牺牲性能,但这需要程序员以一种新的眼光来研究程序设计。对新程序员 来说,命令式程序设计通常是一个更为自然和直观的起点,这就是为什么大部分程序设计说明都集中关注命令式语言和方法的原因。 不过,随着程序越来越复杂,递归程序设计能够让程序员以可维护且逻辑一致的方式更好地组织代码。

    References
    MeasureMeasure

    展开全文
  • 递归算法总结

    千次阅读 2019-04-30 14:24:34
    1 递归算法初探 本段内容大部分摘自《linux C一站式编程》,作者是宋劲松老师,我认为这是目前看到的国内关于linux C编程的最好的一本技术书籍,强烈推荐! 关于递归的一个简单例子是求整数阶乘,n!=n*(n-1)!,0!=...

    1 递归算法初探

    本段内容大部分摘自《linux C一站式编程》,作者是宋劲松老师,我认为这是目前看到的国内关于linux C编程的最好的一本技术书籍,强烈推荐!

    关于递归的一个简单例子是求整数阶乘,n!=n*(n-1)!,0!=1 。则可以写出如下的递归程序:

    int factorial(int n)
    {
        if (n == 0)
            return 1;
        else {
            int recurse = factorial(n-1);
            int result = n * recurse;
            return result;
        }
    }
    

    factorial这个函数就是一个递归函数,它调用了它自己。自己直接或间接调用自己的函数称为递归函数。如果觉得迷惑,可以把factorial(n-1)这一步看成是在调用另一个函数--另一个有着相同函数名和相同代码的函数,调用它就是跳到它的代码里执行,然后再返回factorial(n-1)这个调用的下一步继续执行。

    为了证明递归算法的正确性,我们可以一步步跟进去看执行结果。记得刚学递归算法的时候,老是有丈二和尚摸不着头脑的感觉,那时候总是想着把递归一步步跟进去看执行结果。递归层次少还算好办,但是层次一多,头就大了,完全不知道自己跟到了递归的哪一层。比如求阶乘,如果只是factorial(3)跟进去问题还不大,但是若是factorial(100)要跟进去那真的会烦死人。

    事实上,我们并不是每个函数都需要跟进去看执行结果的,比如我们在自己的函数中调用printf函数时,并没有钻进去看它是怎么打印的,因为我们相信它能完成打印工作。我们在写factorial函数时有如下代码:

    ...
    int recurse = factorial(n-1);
    int result = n * recurse;
    ...
    

    这时,如果我们相信factorial是正确的,那么传递参数为n-1它就会返回(n-1)!,那么result=n*(n-1)!=n!,从而这就是factorial(n)的结果。

    当然这有点奇怪:我们还没写完factorial这个函数,凭什么要相信factorial(n-1)是正确的?如果你相信你正在写的递归函数是正确的,并调用它,然后在此基础上写完这个递归函数,那么它就会是正确的,从而值得你相信它正确。

    这么说还是有点玄乎,我们从数学上严格证明一下factorial函数的正确性。刚才说了,factorial(n)的正确性依赖于factorial(n-1)的正确性,只要后者正确,在后者的结果上乘个n返回这一步显然也没有疑问,那么我们的函数实现就是正确的。因此要证明factorial(n)的正确性就是要证明factorial(n-1)的正确性,同理,要证明factorial(n-1)的正确性就是要证明factorial(n-2)的正确性,依此类推下去,最后是:要证明factorial(1)的正确性就是要证明factorial(0)的正确性。而factorial(0)的正确性不依赖于别的函数调用,它就是程序中的一个小的分支return 1;这个1是我们根据阶乘的定义写的,肯定是正确的,因此factorial(1)的实现是正确的,因此factorial(2)也正确,依此类推,最后factorial(n)也是正确的。

    其实这就是在中学时学的数学归纳法,用数学归纳法来证明只需要证明两点:Base Case正确,递推关系正确。写递归函数时一定要记得写Base Case,否则即使递推关系正确,整个函数也不正确。如果factorial函数漏掉了Base Case,那么会导致无限循环。

    2 递归经典问题

    从上一节的一个关于求阶乘的简单例子的论述,我们可以了解到递归算法的精髓:要从功能上理解函数,同时你要相信你正在写的函数是正确的,在此基础上调用它,那么它就是正确的。下面就从几个常见的算法题来看看如何理解递归,这是我的一些理解,欢迎大家提出更好的方法。

    2.1)汉诺塔问题

    汉诺塔问题是个常见问题,就是说有n个大小不等的盘子放在一个塔A上面,自底向上按照从小到大的顺序排列。要求将所有n个盘子搬到另一个塔C上面,可以借助一个塔B中转,但是要满足任何时刻大盘子不能放在小盘子上面。

    基本思想分三步,先把上面的N-1个盘子经C移到B,然后将最底下的盘子移到C,再讲B上面的N-1个盘子经A移动到C。总的时间复杂度f(n)=2f(n-1)+1,所以f(n)=2^n-1。

    void hano(char a, char b, char c, int n) {
        if (n > 0) {
            hano(a, c, b, n-1);
            move(a, c);
            hano(b, a, c, n-1);
        }
    }
    
    void move(char a, char b)
    {
        cout << a << "->" << b << endl;
    }
    

    2.2)求二叉树的深度

    这里的深度指的是二叉树从根结点到叶结点最大的高度,比如只有一个结点,则深度为1,如果有N层,则高度为N。

    int depth(struct node* root)  
    {  
        if (root == NULL)  
            return 0;  
        else {  
            int lDepth = depth(root->left);  //获取左子树深度  
            int rDepth = depth(root->right); //获取右子树深度  
            return lDepth>rDepth? lDepth+1: rDepth+1; //取较大值+1即为二叉树深度  
        }  
    }  
    

    那么如何从功能上理解depth函数呢?我们可以知道定义该函数的目的就是求二叉树深度,也就是说我们要是完成了函数depth,那么depth(root)就能正确返回以root为根结点的二叉树的深度。因此我们的代码中depth(root->left)返回左子树的深度,而depth(root->right)返回右子树的深度。尽管这个时候我们还没有写完depth函数,但是我们相信depth函数能够正确完成功能。因此我们得到了lDepth和rDepth,而后通过比较返回较大值加1为二叉树的深度。如果不好理解,可以想象在depth中调用的函数depth(root->left)为另外一个同样名字完成相同功能的函数,这样就好理解了。注意Base Case,这里就是当root==NULL时,则深度为0,函数返回0

    2.3)判断二叉树是否平衡

    一颗平衡的二叉树是指其任意结点的左右子树深度之差不大于1。判断一棵二叉树是否是平衡的,可以使用递归算法来实现。

    bool is_balanced(BinaryTreeNode* pRoot)
    {
        if(pRoot == NULL) //基本情况,为空的话,返回true
            return true;
     
        int left = depth(pRoot->m_pLeft);
        int right = depth(pRoot->m_pRight);
        int diff = left - right; //计算左右子树深度之差
        if(diff > 1 || diff < -1) //如果深度之差大于1返回false
            return false;
     
        return is_balanced(pRoot->m_pLeft) && is_balanced(pRoot->m_pRight); //递归判断左右子树,注意是&&,即左右子树都必须是平衡的这棵二叉树才是平衡的
    }
    

    该函数的功能定义是二叉树pRoot是平衡二叉树,即它所有结点的左右子树深度之差不大于1。首先判断根结点是否满足条件,如果不满足,则直接返回false。如果满足,则需要判断左子树和右子树是否都是平衡二叉树,若都是则返回true,否则false。

    上面代码性能不高,会重复遍历结点,一个改进的算法是采用后序遍历的方式遍历树的结点,在遍历到本结点前我们已经遍历完了它的左右子树,我们只需要在遍历的时候记录结点的深度,就可以一边遍历一边判断该结点是否是平衡的。代码如下:

    bool is_balanced_2(BinaryTreeNode* pRoot, int* pDepth)
    {
        if(pRoot == NULL)
        {
            *pDepth = 0;
            return true;
        }
     
        int left, right;
        if(is_balanced_2(pRoot->m_pLeft, &left) //左子树平衡
            && is_balanced_2(pRoot->m_pRight, &right)) //右子树平衡
        {
            int diff = left - right;
            if(diff <= 1 && diff >= -1)
            {
                *pDepth = 1 + (left > right ? left : right);
                return true;
            }
        }
     
        return false;
    }
    

    该函数功能定义是返回以pRoot为根的二叉树是否是平衡二叉树,同时把树的深度保存在pDepth指向的值中。基本情况是树为NULL,则深度为0,返回true。否则只有左右子树都是平衡的情况下,深度分别存在变量left和right中,判断左右子树的深度之差是否不大于1,如果是则返回true,注意还要设置树的深度值。

    调用的函数定义如下:

    bool IsBalanced(BinaryTreeNode* pRoot)
    {
        int depth = 0;
        return is_balanced_2(pRoot, &depth);
    }
    

    2.4)排列算法

    排列算法也是递归的典范,记得当初第一次看时一层层跟代码,头都大了,现在从函数功能上来看确实好理解多了。先看代码:

    void perm(int a[], int k, int N) { //k为起始位置,N为数组大小
        if (k == N-1) { 
            output(a, N); //输出排列
        } else {
            for (int i=k; i<N; i++) {
                swap(a, i, k); //交换
                perm(a, k+1, N); //下一次排列
                swap(a, i, k); //恢复原来的序列
            }
        }
    }
    

    首先明确的是perm(a, k, N)函数的功能:输出数组a从位置k开始的所有排列,数组长度为N。这样我们在调用程序的时候,调用格式为perm(a, 0, N),即输出数组从位置0开始的所有排列,也就是该数组的所有排列。基础条件是k==N-1,此时已经到达最后一个元素,一次排列已经完成,直接输出。否则,从位置k开始的每个元素都与位置k的值交换(包括自己与自己交换),然后进行下一次排列,排列完成后记得恢复原来的序列。

    假定数组a大小N=3,则程序调用perm(a, 0, 3)可以如下理解:
    第一次交换0,0,并执行perm(a, 1, 3),执行完再次交换0,0,数组此时又恢复成初始值。
    第二次交换1,0(注意数组此时是初始值),并执行perm(a, 1, 3), 执行完再次交换1,0,数组此时又恢复成初始值。
    第三次交换2,0,并执行perm(a, 1, 3),执行完成后交换2,0,数组恢复成初始值。

    也就是说,从功能上看,首先确定第0个位置,然后调用perm(a, 1, 3)输出从1开始的排列,这样就可以输出所有排列。而第0个位置可能的值为a[0], a[1],a[2],这通过交换来保证第0个位置可能出现的值,记得每次交换后要恢复初始值。

    如数组a={1,2,3},则程序运行输出结果为:1 2 3 ,1 3 2 ,2 1 3 ,2 3 1 ,3 2 1 ,3 1 2 。即先输出以1为排列第一个值的排列,而后是2和3为第一个值的排列。

    2.5)组合算法

    组合算法也可以用递归实现,只是它的原理跟0-1背包问题类似。即要么选要么不选,注意不能选重复的数。完整代码如下:

    #include<iostream>
    using namespace std;
    #define N 3  //数组大小为3
    int select[N] = {0}; //选择数组,用于存储数组哪些数字被选中。
    /*输出数组中选中的数*/
    void output(int a[], int n)
    {
        for (int i=0; i<n; i++) {
            if (select[i])
                cout << a[i] << " ";
        }
        cout << endl;
    }
    /*数组a从位置i开始选取k个数*/
    void combination(int a[], int i, int k)
    {
        if (i > N) return; //位置超出数组范围直接返回,否则非法访问会出段错误
        if (k == 0) {  //选取完了,输出选取的数字
            output(a, N);
        } else {
            select[i] = 1;  
            combination(a, i+1, k-1); //第i个数字被选取,从后续i+1开始选取k-1个数
            select[i] = 0;
            combination(a, i+1, k); //第i个数字不选,则从后续i+1位置开始还要选取k个数
        }
    }
    
    /*组合主函数,包括选取1到n个数字*/
    void combination_helper(int a[], int n) {
        for (int k=1; k<=n; k++) {
            combination(a, 0, k);
        }
    }
    
    int main()
    {
        int a[N] = {1, 2, 3};
        combination_helper(a, N);
        return 0;
    }
    

    2.6) 逆序打印字符串

    这个比较简单,代码如下:

    void printReverse(const char *str) {
      if (!*str)
        return;
      printReverse(str + 1);
      putchar(*str);
    }
    

    3 多说一句

    对递归有兴趣的,还可以看看这篇文章,用递归实现链表逆序

    参考资料

    • 宋劲松《Linux C编程》递归章节

     

    --------------------------------------------------------------------------------------------------------------------------------------------------

    递归实现斐波那契数列(一):

    在数学上,斐波纳契数列以如下被以递归的方法定义: 
    F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)

    使用递归实现
    很直观表示方式,用递归很容易实现:

    function f($a)
    {
        if ($a == 0 || $a == 1) {
            return 1;
        }
        return f($a-1) + f($a-2);
    }

    for($i = 0; $i < 70; ++$i)
    {
        echo f($i).' ';
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    但是运行的时候,发现上面代码运行会超时:

    递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解,容易编程。但递归是用栈机制实现的,每深入一层,都要占去一块栈数据区域,对嵌套层数深的一些算法,递归会力不从心,空间上会以内存崩溃或超时而告终,而且递归也带来了大量的函数调用,这也有许多额外的时间开销。所以在深度大时,它的时空性就不好了。

    那么如果非要用递归,有什么办法可以改进呢?

    可以看到,在打印的过程中,比如求 f(6) 调用 f(5) 和 f(4)时,之前的某次循环其实已经算出来了 f(5) 和 f(4) ,不需要再算了。

    可以使用一个数组,来保存之前的结果

    function f($n, $arr)
    {
        global $arr;
        if( isset($arr[$n]) ) {  //比 array_key_exits()效率高
            return $arr[$n];
        }
        return f($n-1, $arr) + f($n-2, $arr);
    }
    $arr = [
        0 => 1,
        1 => 1,
    ];
    for($i = 0; $i < 1000000; ++$i)
    {
        $arr[$i] = f($i, $arr);
        echo f($i, $arr).' ';
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    使用PHP7,打印1000000个也没有问题。

    使用循环实现
    <?php 
    $arr[1] = 1;
    for($i = 2;$i < 100;$i++)
    {
        $arr[$i] = $arr[$i-1] + $arr[$i-2];
    }
    echo join(",",$arr);  //将数组合并为一个字符串输出
    ?>
    1
    2
    3
    4
    5
    6
    7
    8
    非递归实现比递归效率高很多。

    递归和循环的简单比较:
    1、从程序上看,递归表现为自己调用自己,循环则没有这样的形式。
    2、递归是从问题的最终目标出发,逐渐将复杂问题化为简单问题,并且简单的问题的解决思路和复杂问题一样,同时存在基准情况,就能最终求得问题,是逆向的。而循环是从简单问题出发,一步步的向前发展,最终求得问题,是正向的。
    3、任意循环都是可以用递归来表示的,但是想用循环来实现递归(除了单向递归和尾递归),都必须引入栈结构进行压栈出栈。
    4、一般来说,非递归的效率高于递归。而且递归函数调用是有开销的,递归的次数受堆栈大小的限制。

    递归实现斐波那契数列(二):

    简介      
    斐波那契数列(Fibonacci Sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)。我用递归和迭代两种方法实现了斐波那契数列

    实现代码(php)
    <?php
     
    class Fibonacci
    {
     
        /**
         * Description:迭代方法获取fibonacci第n项数值
         *
         * @param int $n            
         * @return int
         */
        public static function fib_interation ($n)
        {
            $fib = array(); // 定义fibonacci数组
            
            if ($n < 0) {
                return 0;
            }
            
            for ($fib[0] = 0, $fib[1] = 1, $i = 2; $i <= $n; $i ++) {
                $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
            }
            
            return $fib[$n];
        }
     
        /**
         * Description:递归方法获取fibonacci第n项数值
         *
         * @param int $n            
         * @return int
         */
        public static function fib_recursive ($n)
        {
            if ($n <= 0) {
                return 0;
            } elseif ($n == 1) {
                return 1;
            } else {
                return self::fib_recursive($n - 1) + self::fib_recursive($n - 2);
            }
        }
    }
     
    $fib1 = Fibonacci::fib_interation(5);
    echo $fib1 . "\n";
     
    $fib2 = Fibonacci::fib_recursive(10);
    echo $fib2 . "\n";
     
    ?>

    运行结果


    缺点
    今天看道这篇博客浏览量还挺高,因此重构了一下代码,半年前的水平确实差,代码看着就恶心,今天重构一下!
    其次,编程之美上介绍了一种分治策略求fibonacci的方法,不过我没掌握,有兴趣的同学可以贴出实现代码讨论一下,建议c或者php!

    展开全文
  • 递归算法要素

    2020-10-14 16:17:26
    每次写递归,都按照这三要素来写,可以保证写出正确递归算法! 1. 确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么...
  • 递归算法

    2014-08-09 17:06:18
    递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。   能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它...
  • 实验二 递归算法设计与应用 一. 实验目的和要求 1. 加深对递归算法的理解,并针对具体问题设计算法; 2. 分析算法的复杂性,寻找比较高效的算法,并实现。 3. 分析格雷码问题,并设计递归算法求解之。 二. 基本...
  • 前面在Topcoder上面看到一道题,是用到递归,于是说仔细学习一下递归算法,想到汉诺塔应该是最入门的递归,结果折腾了半天写出来 。最后去找了个正确答案。最后虽然似乎看懂了,但自问个人真是写出来。所以就贴...
  • 递归算法思想

    2016-06-27 16:31:19
    在知乎上面搜索递归,但是普遍的回答是业务开发中常涉及,和for循环差不多,消耗性能太大,推荐使用。本着不服管的性格,我差了一些有用的资料,和大家分享下,递归算法和使用场景。为什么要用递归编程里面...
  • 递归算法分析-最简单的例子

    万次阅读 2021-08-20 14:40:38
    递归算法在算法设计中,是一种比较难以理解的算法存在,感觉递归算法无限套娃,最终居然也能返回正确结果,对于初入坑的童靴是一个神一般的存在。本文通过对递归算法的一个例子,从最简单的例子中,逐步撕开其神秘...
  • 递归算法转换为非递归算法的技巧

    千次阅读 2017-11-22 00:00:00
    递归函数具有很好的可读性和可维护性,但是大部分情况下程序效率不如非递归函数,所以在程序设计中一般喜欢先用递归解决问题,在保证方法正确的前提下再转换为非递归函数以提高效率。 函数调用时,需要在栈中...
  • 一文读懂递归算法

    万次阅读 多人点赞 2018-06-01 14:48:40
    递归的学习绝对是一个持久战,没有人可以一蹴而就。一年两年的,很寻常。问题的复杂,加上递归本身的细节,我们想要 '学会','学好',再 '用好',是需要一个漫长的过程的。所以还希望读者有足够的耐心。一:什么是...
  • 递归算法知识点总结

    2020-05-23 17:37:46
    例如求n的阶乘等,问题的求解过程可以将其递归定义直接转换为对应的递归算法。 2.数据结构是递归的 如单链表等 3.问题的求解方法是递归的 如:是在有序数组中查找一个数据元素是否存在的折半查找算法 ...
  • 递归算法实现

    千次阅读 2017-05-21 14:07:13
    递归算法 1、一个人赶着鸭子去每个村庄卖,每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子,问他出发时共赶多少只鸭子?经过每个村子卖出多少只鸭子?  题目分析: 递归终止的条件是...
  • 递归算法的学习

    2015-11-17 14:22:54
    此之前对递归的认识: ...题目:编写函数void reverse(string&s),用递归算法使字符串s倒序 一开始思考进行怎么做时就觉得参数不够用,函数的形式不正确,因为没法对字符串的下标进行迭代。然后写了个辅助函
  • 算法导论------递归算法的时间复杂度求解

    万次阅读 多人点赞 2016-12-04 19:31:11
    1.算法设计与分析概述  在总结递归算法的时间复杂度分析之前,应该明确几组概念。...  非递归算法时间复杂度分析较为简单,通常是计算算法中基本语句执行次数,一般都是一个关于问题规模n的表达式,
  • 递归算法的优缺点.pdf

    2020-07-16 06:44:45
    实用标准文案 递归算法的优缺点 1 优点 结构清晰可读性强而且容易用数学归纳法来证明算法的正确性 因此它为设计 算法调试程序带来很大方便 2 缺点 递归算法的运行效率较低 无论是耗费的计算时间还是占用的存储空间都...
  • 算法设计与分析之递归算法

    千次阅读 2020-11-26 22:40:27
    简单易懂的介绍了递归算法的原理和设计方法
  • (1)假设二叉树采用链接存储方式存储,分别编写一个二叉树先序遍历的递归算法和非递归算法。 (2)一棵完全二叉树以顺序方式存储,设计一个递归算法,对该完全二叉树进 行中序遍历。 3.解题思路 (1)采用...
  • 递归算法总结JAVA

    千次阅读 2017-03-20 13:33:11
    java递归算法总结  原文地址:http://blog.csdn.net/tomcat_2014/article/details/51113740 作者:toMatser 1.何为递归 个人理解就是自己调用自己,直到满足一个条件结束自己调用自己的过程,这个就是递归。...
  • 递归算法的讲解

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

    千次阅读 多人点赞 2018-05-24 10:51:21
    对一些简单的递归问题,我们总是惊叹于递归描述问题的能力和编写代码的简洁,但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。在正式介绍递归之前,我们首先引用...
  • Python递归算法详解

    万次阅读 2019-06-22 22:31:23
    Python递归算法详解 2018.08.05 17:501296浏览 递归的概念很简单,如果函数包含了对其自身的调用,该函数就是递归的。 递归(Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。 在...
  • 递归算法的原理

    千次阅读 2017-06-19 17:17:15
    递归算法:顾名思义,递和归;其实际也是根据栈的原理,后进先出,保证函数的返回值正确; 就拿斐波那契数列进行举例说明: 斐波那契数列算法,如:1,1,2,3,5,8,13,21…… ,可以看到这里面的规律...
  • 第一种情况就是正常的递归算法,解除递归限制: import sys sys.setrecursionlimit(1000000) 1.那什么是递归算法呢,满足了什么条件就是递归算法呢? 必须的条件: 一、函数调用自身 二、设置了正确的返回条件 2. ...
  • 全排列的递归算法

    万次阅读 多人点赞 2012-06-14 15:26:11
    前面我们介绍了全排列的非递归算法,现在我再来写一下全排列的递归算法: 这两种算法的算法思路并相同。递归算法的思路比较接近于我们现实生活中的思路。 1.试想,我们只有两个数字:12.要对它进行全排列,第一...
  • 目录递归介绍递归求阶乘递归求斐波那契递归解决汉诺塔总结 递归介绍 递归:就是函数自己调用自己。...递归函数需要有临界停止点,即递归不能无限制的执行下去。通常这个点为必须经过的一个数。 递归通常能被其他...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 107,409
精华内容 42,963
关键字:

关于递归算法不正确的是