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

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

    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)描绘了一个扭曲的城市,其中包含一个递归包含图片的画廊,因此无限。

    更多相关内容
  • 递归 一个函数在执行过程中一次或多次调用其本身便是递归,就像是俄罗斯套娃一样,一个娃娃里包含另一个娃娃。 递归其实是程序设计语言学习过程中很快就会接触到的东西,但有关递归的理解可能还会有一些遗漏,下面...
  • 递归图(reecurrence plots),从相空间重构时间序列的matlab程序,
  • 递归

    千次阅读 2020-11-03 23:35:25
    1、递归基本概念 递归的意思就是不停的调用自己,但是我们要知道的是我们的计算机资源是有限的,一般来说递归的层数不能太深(特别是自己写的程序有问题容易资源耗尽!)。递归通常来说是程序写着简洁但是人的思维...

    1、递归基本概念

            递归的意思就是不停的调用自己,但是我们要知道的是我们的计算机资源是有限的,一般来说递归的层数不能太深(特别是自己写的程序有问题容易资源耗尽!)。递归通常来说是程序写着简洁但是人的思维量比较大同时计算机的执行效率没有直接写的代码效率高,因为存在函数的不停调用,在计算内部调用函数是开销比较大的。什么是递归什么是自己调用自己,举个简单的例子:

    int mul(int x){
        x--;
        mul(x);
    }

    我们能够清晰的看见上面的程序存在自己调用自己的情况,那么这种就叫做递归,只是上面的递归并不规范!甚至是有问题的,为什么呢?因为我们思考一下这个函数的执行过程如下:

    当我们传入x = 5

    第一次执行:x--   --------> x变成了4,然后再调用自己,x=4作为参数传入

    第二次执行:x--  ---------->x变成了3,然后再调用自己,x=3作为参数传入

    。。。

    这个程序永远不会结束,

    所以从上面的例子我们可以看出来写递归喝循环一样,必须要有个结束条件,我们称之为出口!加入现在我有一道题目是我要求解一个数的阶乘,那么我们的递归程序可以写成:

    // 先写一个简单的,这是个全局变量
    int result = 1;
    
    void mul(int x){
        // 这就是我们说的出口
        if(x==0) return;
        
           
        result *= x;
    
        // 递归
        mul(x-1);
    }

    你可能会说上面这个例子我用一个循环就很好的解决了,确实是递归大部分能转化成循环(特别是while循环,但是你的思考量将会提高N倍!!!)递归可以让我们不用纠结于中间的复杂过程,你只用专注于分支条件和出口即可!

            现在我们来优化上面的简单的递归程序,通常我们的c语言中不喜欢用全局变量,但是程序再递归的时候,我们需要的有记忆的变量不能直接申请再函数中(有记忆的变量是指函数每次调用自己的时候需要上一次的值,不能被刷新!我还是举例说明吧:),如果上面的程序我写成:

    void mul(int x){
    
        if(x == 0) return;
    
        // 不能这么写,每次都被刷新了,
        int result = 1;
    
        result *= x;
    
        mul(x-1);
    }

    那么对于这种需要有记忆的变量我们递归通常把其作为参数!让参数帮助我们记忆,所以上面的程序可以优化成:

    阶乘递归版本1:

    void mul(int x, int result){
        if(x == 0) return;
    
        result *= x;
    
        // 这样就每次帮我们记住了乘积并且传入到了下一次
        mul(x-1,result);
    }

    当然上面的程序是有问题的,不过问题不在递归,就递归这个问题来说上面的程序是比较优秀的写法了。(问题在于c语言是传值的,穿进去的变量在函数里面修改了在外面是看不出来效果的!)

    在提供一个上面的递归版本:

    阶乘递归版本2:

    int mul(int x){
    
        if(x == 1) return 1;
    
        return x* mul(x-1);
    }

    着两个版本版本2看着好像简单一些,但是版本1的效率要高很多:

    版本1:尾递归,递归的程序放在函数的最后面,并且递归不在任何的表达式中,如版本1

    版本2:普通递归,递归的程序不在函数肚饿尾部,或者说在一个表达式中,效率不如尾递归。

    详细的可以自己百度!!!

     

    至此我们知道了递归最重要的东西:

          1、出口

          2、如何记住需要有记忆的变量

    2、为什么要有递归?

    就像刚才的例子你肯定会说递归很麻烦,但是我想说的是你naive了,递归真正的优点是:

    1、缩小问题的规模

    2、可以让我们不用思考中间过程

    直接用题目举例:

    100梯的阶梯,我现在每次能走1步或者2步,那么我有多少种走法呢?

    解题思路:

    从100梯往回思考:

    你只能是  99----->100. step(99)+1

                     98----->100 step(98)+2

    在从99往回思考:

    98----->99. step(98)+1

    97----->99. step(97)+2

    我觉得你应该发现什么了,最关键的是

    step(i) = step(i-1) + step(i-2)

    第i梯只有两种走法能够走到,那就是i-1走一梯,i-2走两梯

    所以程序是:

    int step(int x){
        
        // 出口有两个
        if(x == 1) return 1;
        if(x == 2) return 2;
    
        // 这个算什么递归呢?
        return step(x-1)+step(x-2);
    }

    上面的代码有两个出口,因为第一梯只有一种走法,我们非常的确定,第二梯有两走走法(1+1 或者 2),我们也非常的确定。然后中间的过程我们就不用考虑了!!!!

    现在问个问题:上面的递归属于尾递归还是普通递归????

    总结:递归通常来说就是由分支条件+出口+状态的递归构成!

     

    题目1、

    输入一个数组,输出数组中数据的所有全排列组合!!

    例如:

    输入:[1,2]

    输出:[1,2]、[2,1]

     

    样例2、

    输入:[1,2,3]

    输出:[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]

    一次类推

    上面的题目一只是运用了递归的不用考虑中间过程

    3、递归与暴力美学

            通常来说我们的递归可以暴力解决很多的题目并且不需要我们过多的纠结与中间的过程,这就是递归的优点,什么叫暴力呢?对于任何一个编程问题,我们认为其有解那么必定就是存在一种从开始到结束的状态序列。 举例说明我们下围棋,为什么机器能够战胜人类?其实机器战胜人类是必然的,为什么呢?如果步考虑计算机资源的限制我直接暴力列举出从开始下棋到结束下棋的每个局面,然后根据人的走不自动匹配路径即可。这里的棋局就可以看成一个状态:

    如上图是围棋的开局,我们可以看成是一个其实状态,那么接下来的一个状态就可能有19*19种可能(围棋的棋盘式19*19),当人走出了第一步之后,现在棋局又回归到了相同的问题:在一个棋盘上计算机需要走出最有利(或者说更加接近赢面的棋局,这就是递归)。此时计算机又19*19-1(种可能)

    任何问题的解都可以抽象成上述的一个树形的解空间,像这种我们用循环式无法求解的,因为首先是训话你的次数不知道,其次循环无法表示这种层级的结构,如果每个状态都是相似的问题或者局面,那么我们使用递归肯定能构造出(列举出)解空间的所有可能,因此必定能解决这个问题,只是时间复杂度可能有时候比较高,但是这并不能阻挡这个美丽的方法!

     

    3.1、使用举例:

    我们就着上面的讲解做一个题目,假定现在在一个棋盘上下五子棋,你执白,计算机执黑,现在要求你判断某个局面你们谁赢了。

    每个棋局的局面用一个二位数组输入,白棋用1代表,黑棋用2代表,空位置用0代表

    样例1、

    输入:(12*12的数组)

    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 2, 2, 2, 1, 0, 0, 0]
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 0, 0]
    [0, 0, 2, 1, 0, 1, 1, 2, 0, 0, 0, 0]
    [0, 0, 2, 0, 1, 0, 1, 2, 0, 0, 0, 0]
    [0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 

    上面的棋局黑方连成5个,那么计算机获胜!!!

    输出:计算机胜

    现在我们一起来分析这个题目:

    TIPS:注意五子棋可以斜着来的!!!

    解题思路:

    我们直接用一个循环遍历所有的位置,当遇见当前位置不是0,那么说明有人下棋了,假定下棋的是你,也就是该位置是1,那么你就需要判断周围的情况,那么此时你就可以假设你自己会试探型的去挪动到周围的一位位置,挪动后你会发现你又面临相同的问题------判断周围的情况!显然这就是递归,那么借助上面的思路我们的代码大概可以长成这样:

    int n = 12;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
    
            if(chess[i][j] == 1){
                //需要递归
                whiteWin(chess,i,j,1);
            }
    
        }
    }
    
    
    //递归的函数
    //第一个参数是棋盘数组
    //第二个参数是行,第三个参数是列
    //第四个参数是,数我们已经几颗棋子连在一起了
    
    bool whiteWin(int [][]chess,int i,int j,int count){
    
        if(chess[i][j] != 1){
            //已经5子连珠
            if(count == 5) return true;
            else return false;  //没有,但是前面也不是白棋了,不能继续前进了
        }
        
    
        // 向左边前进,这就是递归,我们传入的棋盘数组是不会改变的,不停改变的就是我们当前处于
        // 哪一颗棋子,也就是i和j,那么这次往左边走就是 j-1,count+1代表的是当前路径连接的
        // 棋子增加了一颗
        bool left = whiteWin(chess,i,j-1,count+1);
        
        //同理自己写其余几个方向!!!!
        
        // 最后返回8个方向的综合后的结果,只要有一个满足就行了
        return left || right ||... 
    }

    请你下去不全剩余的代码!!!!!!

    4、递归与问题规模的缩小

            上面的暴力美学美归美,但是并不是任何时候都是可取的,比如就是下棋的时候,列举所有棋局的可能至少在目前的计算机内存肯定是远远不够的,那么我们在解决其他的问题也是类型的,我们需要将问题的规模逐步缩小,然后求解缩小后的规模,比如我举个例子,我们可以使用递归的方式来遍历一个数组!

    假定数组是:1,2,3,4,5,6,7,8,9

    void dis(int []data,int index){
        
        printf("%3d",data[index]);
        
        //当然这里不是很贴切,数组index前面的部分就已经没用了,我们接下来面对的问题规模就是
        //数组长度-index
        dis(data,index+1);
    }

    我们每次输出一个数据后,假定该数据就不见了,那么数组的长度在不停的变短,这就是问题规模的缩小!!!

    很简单的例子上面的爬梯子就是这类型的,问题规模被我们不断的缩小,下面我再给出一个案例:

    假定我现在要对一个数组进行排序:

    8,11,9,12,3,23,32,17,5

    我们都学过冒泡排序,但是这个并不够快,我提供一个思路:

    我们是否可以将数据分组,然后再分组内排序后再合并,因为分组和两边的工作是可以同时进行的(现实中确实这样比你一个计算机排序快,这就好比我可以用多台计算机一起协作的做同一个事情),我们先分为:

    8,11,9,12,3

    23,32,17,5

    然后再分:

    8,11,9

    12,3

    23,32

    17,5

    上面4组就非常的好排序,我们将一个问题规模比较大的问题分解为了几个规模较小的问题,我们先解决小问题然后再合并解就行了。

    合并过程举例:

    例如排好序后是:

    8,9,11

    3,12

    23,32

    5,17

    然后我们两来那个合并:

    ---》3,8,9,11,12

    ---》5,17,23,32

    然后再合并

    我们可以看出来分解问题和合并解的过程都是一个递归的过程(每个状态面度爹问题规模都是一样的!)

     

     

    5、递归与回溯

           什么叫回溯呢?举个简单的例子就是你走迷宫,最古老有效的办法就是在你身上拴一根绳子,然后你遇见岔路口就随便选一个,走到头出不去,那么就回头沿着绳子的方向回到上一个岔路口再选择下一个路口继续前进!对没错沿着原路返回,时空倒流这就是回溯,为什么要有这个呢,例如这道题目:

            到底走到了一个位置我应该怎么走呢?(有两种选择),你不可能保证你每次的选择就是最优秀的,有的人说我可以选择当前代价最小的方向前进呀!!但是问题是当前代价最小的位置后面的位置可能让你付出惨痛的代价,不要目光短浅,要全局考虑!因此最好的办法就是每次走到头,发现不行了再倒回去,把前面做的所有的事情全部回归原样,这样就好像时光倒流了一样(回溯),但是你已经可以知道这个岔路口出不去了,我们不要走它....以此类推,这就是回溯,类似上面的全排列我们也做了回溯的操作!

    关键点就在最后一个for循环里面,我们把所有的代选择的决策全部放在里面遍历,经典的回溯题目举例:

    题目1、

    自己百度leetcode,进入英文的那个,不要进入力扣中文的!需要你注册账号

    leetcode 第51题 (这个刷题网站题目比较难,我叫你做多少你就做多少)

     

    TIPS:记住我和你说的写递归的代码风格:

    递归的函数:

             出口结束条件

             违法判断

            作出选择

           递归

           撤销选择

    请务必按照上面的风格进行编写代码!!!!!!!

    还有就是带返回值的递归比不带返回值的递归难,如果不是很清楚就把想返回的值放在参数重,用指针传递,想要获取或者修改的时候都能反应到外部!!

     

     

    6、递归的加速---剪枝

            剪枝的由来其实很简答, 任何问题的解都可以抽象成一个解空间,那么解空间就长这样,其中的一个解就是从根节点到叶子节点的整个路径。但是我们肯定遇见过这种问题:在搜索答案的时候已经发现了当前的这个分支已经不存在了,那么还有必要继续往下匹配下去吗?答案是显然的,我们有时会要学会放弃,就好比你刮奖,如果刮出来了一个谢字那么久没必要往下面刮下去了。

             可能看到这里你已经明白了,剪枝剪枝顾名思义就是把整个解空间树给剪掉一些压根就不可能的节点,因为树状结构的特点,我们的树你越早发现是否合适那么就会节省越多的时间!!因此剪枝要趁早!!越早确认一个节点不行,那么后面少遍历的节点可能是成千上万的,本来递归不停的调用函数效率就低!!

    6.1、剪枝常见手段1----设置阈值

            对于常见的需要我们递归的遍历找最大值和最小值的情况,我们通常在外面(可以是全局变量,也可以通过参数传入)设置一个变量来记录最大值和最小值,如果在遍历的途中就超过这个阈值那么就可以直接舍弃掉后续的遍历,这个的搜索效率会不停的提高,越到后面剪枝的幅度越大,脑补前面剪枝的阈值并不严格,但是随着剪枝次数越来越多,选出来的阈值越来越优秀,这就类似正太分布,大部分的节点都是大于阈值的。

          典型题目:

    https://leetcode.com/problems/cherry-pickup/

    自己百度leetcode,进入英文的那个,不要进入力扣中文的!

    leetcode 第741题(这个刷题网站题目比较难,我叫你做多少你就做多少)

    leetcode 第64题

     

    6.2、剪枝常见手段2---设置标志量

    在有的题目中,我们通常在统计的时候为了避免出现环路,重复的走,会给每个走过的格子都打上标记。举例说明:

    题目1:

    给定一个二维数组,其中全部是0和1,1代表岛屿,0代表海洋,连着的岛屿被认为是一个岛屿(这些岛屿有个特点,都是往右边或者下边延伸的),我们现在要求面积最大的岛屿面积!

    往右边或者下边延伸的意思就是值不会出现:

    输入:

    二维数组:

    1 0 0 1 0 0 0 1

    1 0 1 1 0 0 0 1

    0 0 0 0...

    (具体案例自己举几个测试,我没找到这个题目)

    上面这个的解题思路是,设置一个标志量,bool flag[][];走过的地方都打上true,要是递归遇见了就回去,说明已经走过了!!(因为这道题目并没有说只能往哪个方向走!!)

    题目2:

    https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&&tqId=11218&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

    上面的是牛客网,这个也可以刷一些题目,这道题目是关于回溯比较经典的

    6.3、剪枝常见手段3---利用高速算法找出较好的解

    因为我们的递归通常来说比较慢,我们的初始剪枝速度可能会比较缓慢,如果我们能找到一个高速的算法(解不一定要最优),那么先用高速的算法计算出一个阈值,然后再利用这个阈值剪枝,效果是比较良好的!通常来说我们的高速算法可以选择贪心算法!

    例题:暂时没找到合适的

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 为什么你学不会递归?告别递归,谈谈我的经验

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

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

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

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

    递归的三大要素

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

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

    例如,我定义了一个函数

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    案例1:斐波那契数列

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

    1、第一递归函数功能

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

    int f(int n){
        
    }
    

    2、找出递归结束的条件

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

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

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

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

    所以最终代码如下:

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

    搞定,是不是很简单?

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

    案例2:小青蛙跳台阶

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

    1、第一递归函数功能

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

    int f(int n){
        
    }
    

    2、找出递归结束的条件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    案例3:反转单链表。

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

    链表的节点定义如下:

    class Node{
        int date;
        Node next;
    }
    

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

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

    1、定义递归函数功能

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

    Node reverseList(Node head){
        
    }
    

    2. 寻找结束条件

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

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

    3. 寻找等价关系

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

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

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

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

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

    接下来呢?该怎么办?

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

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

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

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

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

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

    有关递归的一些优化思路

    1. 考虑是否重复计算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    f(1) = 1;

    f(2) = 2;

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

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

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

    最后总结

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

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

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

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

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

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

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

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

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

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

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

    在这里插入图片描述

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

    在这里插入图片描述

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

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

    展开全文
  • 递归程序设计方法.pdf

    2022-06-21 04:58:31
    递归程序设计⽅法 递归程序设计⽅法 (⼀)递归程序设计⽅法的要点 1) 对于含有递归特征的问题,最好设计递归形式的算法。但也不要单纯追求形式。应在算法设计的分析过程中"就事论事"。例如,在利⽤分割求解 设计...
  • 一 、递归算法简介 在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。  递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使...
  • 这几天看到几篇关于尾递归的文章,之前对尾递归没有多大概念,所以回头研究了一下尾递归。  尾递归的概念尾递归(Tail Recursion)的概念是递归概念的一个子集。对于普通的递归,由于必须要记住递归的调用堆栈,...
  • 递归应用C语言实现

    2018-02-09 10:16:44
    包含多个经典的递归应用代码: 1.fibonacci.c 是斐波拉契数列递归解法 2.hanoi.c 是汉诺塔递归算法 3.permutation.c 是全排列递归算法 4.queen.c 是八皇后递归算法 5. reverse.c 是递归的测试代码 6.strlrn.c 是求...
  • 代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间序列进行递归图分析代码 RQA对离散时间...
  • 两种mysql递归tree查询效率-mysql递归tree,提供两种递归算法
  • 二叉树递归递归遍历(递归前中后,非递归前中后,层次遍历)
  • php递归获取子级,父级,无限极分类,带demo,效率超高。下载请评价,谢谢!!!
  • C#使用递归算法,生成并画树形状的图形。详细介绍请到博客中看看
  • 快速选择非递归递归算法实现
  • 第六章 递归算法.ppt

    2020-07-21 00:35:43
    第6章 递归算法 6.1 递归的概念 6.2 递归算法的执行过 6.3 递归算法的设计方法 6.4 递归过程和运行时栈 6.5 递归算法的效率分析 6.6 递归算法到非递归算法的转换 6.7 设计举例 本章主要知识点 递归的概念 递归算法的...
  • java 递归读取文件夹 读取文件 写文件java 递归读取文件夹 读取文件 写文件java 递归读取文件夹 读取文件 写文件java 递归读取文件夹 读取文件 写文件java 递归读取文件夹 读取文件 写文件java 递归读取文件夹 读取...
  • 递归再特定的场景下,非常实用,巧妙的递归设计能解决很多问题,文章主要列出了递归的各种思想和丰富的使用案例!

    递归剖析

    • 递归真的很重要,之前学的时候,学的一知半解,以为真正了解,每次想到递归,就记得一句:返回给函数的调用者,嗯?函数调用者,你是说外部,还是内部啊?疑问太多了,还有就是被告知一句:递归能解决的问题,循环都能解决,所以就更加不重视递归了!直到接触算法后,在解决问题时,最快,最容易理解的解法就是递归,但是此时的递归却是看不太懂为什么要这样做!我先来说下,在算法中遇到可以用递归轻松完成的:希尔排序、归并排序、快速排序、反转链表及各种反转问题、二叉树的深度遍历、二叉树的各种题基本可以用、全排列…还有算法步骤里需要用到,太多了,所以,递归非常重要!“To iterate is human, to recurse divine 迭代是人,递归是神”,接下来,我也是看了很多算法书和视频,重点来整理下递归!

    递归的两个过程

    • 首先“递归”包括两个过程:递“去”的过程,“归”回的过程!先从一个简单的递归函数讲起
    def di_gui(n):
        print(n, "<===1====>")
        if n > 0:
            di_gui(n - 1)
        print(n, '<===2====>')
    
    
    di_gui(5) # 外部调用后打印的结果是?
    
    • 递归的执行过程:首先,递归会执行“去”的过程,只需要满足终止条件,就会一直在函数内,带着更新的参数,调用函数自身,注意:到内部调用函数, 以下面的代码不会被执行,而是暂停阻塞;此时 随着函数每调用一次自身,还没有触发 返回值和到达终止条件,等同于在原来的基础上不断“向下/向内”开辟新的内存空间,记住,每次调用一次函数,就不是处在同一空间(想象下《盗梦空间》里的情景,梦中梦,都是处于不同的空间)
      在这里插入图片描述

    • 什么时候“递”去的过程结束?记住有两种情况>>> 一是:当前这层空间函数全部执行结束(终止条件),二是:执行到了return 返回值,直接返回

    • 重点来理解下,首先是一,看上面的列子,例子中没有return,但是不断的调用后,最终还是停止了,因为最后n=0时,di_gi(0)还是去调用,从上往下执行时,遇到if n>0 它被终止了,走不下去了,表明,自己能到达的这层空间已经全部执行完毕;接下来请原地返回吧,返回到哪里?返回到函数的调用者,好我们返回到 di_gui(0),把“到内部调用函数” 以下的代码全部执行完;执行完,看代码走到末尾,以为走出了最外层函数?注意了,此时它所处的空间并不是最外层哦,因为之前它被调用就在空间里面,所以回到的是 di_gui(1)的这一层空间,现在才是真正的开始“回”,所以继续把di_gui(1)的这一层空间,“到内部调用函数”以下的代码全部执行完,回到di_gui(2)的这一层空间…直到到达最开始 从外部调用,让参数5进入的最外层空间位置,才走出来!表示《盗梦空间》里,柯布醒了!
      在这里插入图片描述
      回来看下,代码输出的结果:5 4 3 2 1 00 1 2 3 4 5 ( 注意00这两个是在同一层空间哦)
      在这里插入图片描述

    • 从内存角度(本质)来分析:每调用一次函数,都会单独开辟一份栈帧空间,递归函数就是不停的开辟和释放栈帧空间的过程,具体来理解下:一个普通函数从执行到结束,就是一个开辟空间和释放空间的过程;而递归函数是在调用最外层函数时,先开辟一个最外层空间,每调用一次自身,就会在最外层空间内,再自己开辟本次的空间(所以递归耗内存)(还有一种说法是,不断的本次空间的基础上再开辟空间,等于是不断的嵌套,其实这两种说法本质上是一样的,因为信息都可以做到不共享),空间之间如果不通过参数传递或者用return 返回值,信息是不共享的,如下图↓↓↓

    在这里插入图片描述
    在这里插入图片描述

    • 递归的数据共享情况:递归每一层间的数据是独立的,不共享,但是可以通过参数或者返回值来形成共享,参数具体在传入的是“引用类型”(比如列表)

    • 递归 必须要有一个出口,如果没有出口就会重复调用,不断的开辟栈帧空间

    # 获取最大递归层数:
    import sys
    res=sys.getrecursionlimit()
    print(res) # 结果:1000
    # sys.setrecursionlimit(800) 可以自己设置最大递归层数
    
    • 解释含有 return 返回值的递归,记住 return的返回流程是:先计算,再返回 ,来看下一段求阶乘的代码:
    def jie_cheng(n):
        if n <= 1:
            return 1
        return n * jie_cheng(n - 1)
        
    print(jie_cheng(5))
    

    在这里插入图片描述

    • return 是返回到函数调用者,递归函数和普通函数也是一样的,所以递归最后一层空间走到尽头(一是:指向完毕,二是:遇到return,回顾一下而已)遇到return,就要开始返回了,返回到它的调用者(即是阻塞的位置),直到回到最外层空间
    • 如果上面的内容看懂了的话,试着解析下:下面这段代码的执行流程
    def get_num(num):
        if num > 2:
            get_num(num - 1)
        print(num)
    
    
    get_num(4) # 输出结果为:2 3 4
    

    在这里插入图片描述

    代码变化一下:

    def get_num(num):
        if num > 2:
            get_num(num - 1)
        else:
            print(num)
    
    
    get_num(4) # 输出结果为 2
    
    '''
    解析一下:加了else后,首先代码区有两个分支,
    在num>2时,执行会有递归,当n=4 是开辟一层空间;
    n=3时开辟一层空间,此时 get_num(2) 再开辟一个空间,
    当它从上往下执行过程中,在他本层空间遇到if num>2 不成立,所以走分支 else,直接打印出来;
    此时代码还没结束,回到上一层空间,num=3, num>2 已经进入了if 不会走else,
    num=4 也不会走else,所以这两层空间没有值输出!
    '''
    

    return 返回值 详解

    • 上面这一大部分,就算是递归入门了,接下来才刚刚开始哦!还要继续讲 return ;先来看下这几段代码:求全排列的一部分递归代码,试着分别写出运行结果,并依次分析原因↓↓↓
    # 例1:
    def fullpermutation(list):
        if list is None:
            return None
        if len(list) == 1:
            return [list]
        res = []
        pivot = list[0]
        remain = fullpermutation(list[1:])
        print(remain)
    
    
    print(fullpermutation([1, 2, 3]))  
    '''
    输出结果为:
    [[3]]
    None
    None
    '''
    
    • 递归只会在两种情况下触发“回”的过程,上述是在最后一层空间是碰到了return,所以给回到它的调用处(阻塞处),因为return会给调用者返回一个值,所以在本层空间,remain接收到了一个值:[[3]];接着执行下面的代码,即是打印remain,所以输出“[[3]]”,执行完print,等于回到了上一层空间,又到了调用处(阻塞处),那么这层空间还有返回值吗?答案是没有,所以“最后一层空间是碰到了return 给它返回的值 只会给最后一层使用”,所以接下来两层都是打印空!
    # 例2:
    def fullpermutation(list):
        if list is None:
            return None
        if len(list) == 1:
            return [list]
        res = []
        pivot = list[0]
        return fullpermutation(list[1:])
    
    
    print(fullpermutation([1, 2, 3]))
    '''
    输出结果为:
    [[3]]
    '''
    
    • 这次是,在最后一层返回时,获得了一个返回值 [[3]] ,然后回到上一层时,前面又有return 表示需要把本层的返回值,返回到上层的接收处,重复,直到回到最外层,这个从底层传上来的返回值,一直传到了最外层,所以才打印出来的,只有最后一层,但是每次一层都获得了返回值,和例子1 后面两层没有返回值是不同的哦!
    # 例3:
    def fullpermutation(list):
        if list is None:
            return None
        if len(list) == 1:
            return [list]
        res = []
        pivot = list[0]
        remain = fullpermutation(list[1:])
        print(list)
    
    
    print(fullpermutation([1, 2, 3]))
    '''
    输出结果为:
    [2, 3]
    [1, 2, 3]
    None
    '''
    
    • 最后一层碰到return,触发会的过程,回到调用处,执行阻塞处下面的代码,打印list,这个list是什么?它就是本层空间 参数的规模(因为代码写的是规模不断变小从[1,2,3]>>>[2,3]>>>[3]),显然,从最后一层回到上一层,此时规模是[2,3],所以打印list 就是[2, 3];接着继续回到上一层,即是最外层,规模是[1,2,3],所以打印[1, 2, 3],最后的None是因为最外层函数,没有返回值,所以才打印出None
    # 例4:
    def fullpermutation(list):
        if list is None:
            return None
        if len(list) == 1:
            return [list]
        res = []
        pivot = list[0]
        remain = fullpermutation(list[1:])
        return list
    
    
    print(fullpermutation([1, 2, 3]))
    '''
    输出结果为:
    [1, 2, 3]
    '''
    
    • 依照上面的步骤,触发回的过程,只要没有到达最外层,return list 返回本层的规模(参数规模),那么这个返回值就会给本层的接收者 remain 不可能给最外层的接收者,虽然这里没有打印 remain的值,但是这里的remain和第一个列子中的remain,后面层数是有返回值的哦(下面例子就会体现),本例,返回到最外层时,list的本层规模为 [1,2,3] 最外层接收者接收到,然后打印出来,所以是[1,2,3]
    # 例5:
    def fullpermutation(list):
        if list is None:
            return None
        if len(list) == 1:
            return [list]
        res = []
        pivot = list[0]
        remain = fullpermutation(list[1:])
        print(remain)
        return list
    
    
    print(fullpermutation([1, 2, 3]))
    '''
    输出结果为:
    [[3]]
    [2, 3]
    [1, 2, 3]
    '''
    
    • 看上面的例子,这次我们是打印了 remain,因为返回的过程中,指向阻塞处(调用处)下面的代码,每次return list 即是 在本层返回 当前的参数规模,所以 remain 是能接收本层的返回值的,所以会打印 [[3]] ,[2, 3] ;最后 [1, 2, 3] 是最外层打印的
    # 例6:
    def fullpermutation(list):
        if list is None:
            return None
        if len(list) == 1:
            return [list]
        res = []
        pivot = list[0]
        remain = fullpermutation(list[1:])
        print(remain)
        print(list)
        return list
    
    
    print(fullpermutation([1, 2, 3]))
    '''
    输出结果为:
    [[3]]
    [2, 3]
    [2, 3]
    [1, 2, 3]
    [1, 2, 3]
    '''
    
    • 这个,就是所有的融合;通过上面的代码我们来总结下return的返回值:最后一层遇到的return 需要执行 回的过程,此时的返回值 值会返回给最后的调用处的接收者;然后执行 阻塞处下面的代码时,如果又遇到return 这里的返回值,如果没有到达最外层,都是给本层的接收者!为什么要大费周章的讲这个,是因为我们在写递归时,往往不清楚return 要怎么写,已及它的返回值是什么?接下来就要看下return 如何解决问题的

    • 请用递归完成一个字符串的反转,输入字符串“abcd”,完成翻转成“dcba”
      除了递归,我们可以直接用字符串的切片来完成,如下,但是这里是要讲递归的思想,不体现方法优劣!

    s="abcd"
    print(s[::-1])
    

    想一下递归的思路该怎么做?
    思路一:按照上面的例子,不断的划分子规模,我们选的是划分原字符串的规模,都是往后截取的,比如第一次参数s=“abcd” 我们取参数s[1:] ,不断调用函数,每次传入参数为:‘bcd’ ‘cd’ ‘d’ ,这样最后一层返回d 我们能拿到最后一个值,然后最后一个返回值d 加上 当前规模的第一个值,就完成了反转,具体代码如下:

    def str_reverse(s):
        if len(s) <= 1: # 递归出口
            return s
        # last = str_reverse(s[1:])
        # return last + s[0]
        return str_reverse(s[1:]) + s[0] # 每次返回最后一层的值,加上当前规模的第一个值
    

    思路二:改变下子规模,我们这次不划分原字符串,而是从它的索引下手,传入最后一个元素的索引,不断去递归索引的值,这时,变的是end的值,从 3 到 2 1 0,到0时触发回的过程,返回当前索引的值,即是 a (不断向前取值),这时我们再加上当前层的s,因为没有划分s所以s每一层都是等于‘abcd’的,我们每次取当前end索引指向的字符串的值,等于从前往后遍历字符串 ‘abcd’ ,两部分链接起来,就完成了反转:每次的返回值为 a, ba , cba, dcba,

    def reve(str, end):
        if end == 0:
            return "" + str[0]
        last = str[end] + reve(str, end - 1)
        return last
    
    
    s = "abcd"
    print(reve(s, len(s) - 1))
    
    • 两种做法都用到return,而是还有重要的递归思路,下面就来看看递归要用什么思路来解

    • 来试下“反转链表”如何用递归做,首先对于一个单链表,要对它反转,我们的思路依旧可以通过不断向后划分子规模,找到它的最后一个结点,然后从后往前依次改变每个结点的指向,让最初的头结点变成尾结点,让它最后指向None;那么具体步骤是:用递归找到最后一个结点,我们可以通过前一个结点的next区域,不断递归,找到下一个结点,直到当前结点的next是None,说明它就是最后一个结点,这也是我们递归的出口,那么依次让它返回,同时改变指向,就完成了,具体看下面的图解:

    class ListNode: 
        def __init__(self, x):
            self.val = x
            self.next = None
    
    
    class Solution:
        def ReverseList(self, pHead):
            if pHead is None: # 判断传入的头结点是否为空
                return None
            if pHead.next is None: # 如果只有一个结点,直接返回结点;同时也是递归的出口
                return pHead
            last_node = self.ReverseList(pHead.next) # last_node永远只接收到了最后一个结点
            pHead.next.next = pHead # 后一个结点,指向前一个结点
            pHead.next = None # 前一个结点,在不同的层,先指向None,如果到达最外层也会指向None
            return last_node # 最后返回最后一个结点,表示反转成功
    
    • 到达最后一层,触发回的过程,返回 last_node 结点给最后第四层,执行阻塞处下面的代码,因为pHead.next.next 是None,它不用改变也行,直接到 return last_node 把 last_node给第三层用…
      在这里插入图片描述
    • 第三层获得 last_node ,执行阻塞处下面的代码,改变指向,pHead.next.next 是“5结点”,它的指针指向 pHead,即是上一个结点,然后上一个结点指向None;因为这里并不需要用一个temp 来保存前一个指针信息,表面上是断开链接,会丢掉数据,其实不会丢掉,因为他们不再同一层;可以用temp先保存前一个结点的数,这属于递归的写,在我的文章>>>反转链表多种解法 有提到,这里不细说!
      在这里插入图片描述
      在这里插入图片描述
    • 直到 回到最外层,起初的头结点,自然会指向None,最后返回 last_node即可
      在这里插入图片描述
    • 这才是 链表反转 递归的详细过程,果然和我开始理解的不一样,当初怎么都无法理解,直到用断点调试,才发现真正的过程,是这样,大家可以用断点调试下,看下代码的具体过程,下面是测试代码:
    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    
    
    class Solution:
        def ReverseList(self, pHead):
            if pHead is None:
                return None
            if pHead.next is None:
                return pHead
            last_node = self.ReverseList(pHead.next)
            print(last_node.val)
            pHead.next.next = pHead
            pHead.next = None
            return last_node
    
        def print_list(self, node):  # 打印测试
            if node is None:
                return None
            while node:
                print(node.val, end="")
                node = node.next
            print()
    
    
    if __name__ == '__main__':
        n1 = ListNode(1)  # 依次实例5个结点
        n2 = ListNode(2)
        n3 = ListNode(3)
        n4 = ListNode(4)
        n5 = ListNode(5)
        n1.next = n2  # 依次将结点链接起来,形成一个链表
        n2.next = n3
        n3.next = n4
        n4.next = n5
        n5.next = None
    
        obj = Solution()
        print(obj.ReverseList(n1).val)
        # obj.print_list(n1) # 1 2 3 4 5
        # obj.print_list(obj.ReverseList(n1))  # 5 4 3 2 1
    

    递归思路

    • 思想:
      1.找到当前这个值与上一个值的关系
      2.找到程序的出口 有个明确的结束条件
      3.假设当前功能已经完成 每次进入更深一层递归时,问题规模相比上次递归都应有所减少

    • 递归思路:
      (1)找重复:看哪一部分是 实现函数的变化;每次进入更深一层递归时,问题规模相比上次递归都应有所减少
      (2)找变化:变化的量应该作为参数
      (3)找边界(出口):终止条件

    • 递归可以分为:
      (1)直接量+小规模子问题
      (2)多个小规模子问题
      (3) “切蛋糕”思维
      (4)找递推公式,等价交换公式

    二分法和递归

    # 二分法一定是在排序好的数据里使用
    
    lst = [33, 22, 44, 55, 66, 88, 77, 99, 101, 238, 345, 456, 567, 678, 789]
    n = 76
    lst.sort()
    left = 0
    right = len(lst) - 1
    
    while left <= right:  # 条件是 开头<=结尾
        middle = (left + right) // 2
        if lst[middle] > n:  # 每次用对折后,中间的数和 查找对象比较
            right = middle - 1
        elif lst[middle] < n:
            left = middle + 1
        elif lst[middle] == n:
            print("找到了")
            break
    else:
        print("这个数不在列表中")
    
    # 递归函数来做
    lst = [22, 33, 44, 55, 66, 77, 88, 99, 101, 238, 345, 456, 567, 678, 789]
    
    
    def func(n, left, right):
        if left <= right:  # 边界
            mid = (left + right) // 2
            if n > lst[mid]:
                left = mid + 1
                func(n, left, right)  # 递归的入口,目的是再确定一次中间的位置
            elif n < lst[mid]:
                right = mid - 1
                func(n, left, right)
            elif n == lst[mid]:
                print("找到了")
                return  # 递归出口
        else:
            print("没有这个数")
            return  # 递归的出口
    
    
    func(66, 0, len(lst) - 1)
    
    # 升级:如果找到了要求的数,请返回它的索引
    
    lst = [22, 33, 44, 55, 66, 77, 88, 99, 101, 238, 345, 456, 567, 678, 789]
    
    
    def func(n, left, right):
        if left <= right:  # 边界
            mid = (left + right) // 2
            if n > lst[mid]:
                left = mid + 1
                return func(n, left, right)  # 每一层都要返回给上一层的调用者
            elif n < lst[mid]:
                right = mid - 1
                return func(n, left, right)
            elif n == lst[mid]:
                print("找到了")
                return mid  # 多层函数只会将返回值返回给上一层的调用者
        else:
            print("没有这个数")
            return -1
    
    
    print(func(66, 0, len(lst) - 1))
    

    尾递归

    尾递归(自己调用自己,且非表达式:把值放到参数中算)
    

    在这里插入图片描述

    >>>求斐波那契数列第n位是几?(尾递归做法)
    
    def feibo(num, res, temp):
         #使用尾递归法求解斐波那契数量的第num个数字
         if num == 0:
              return res
         else:
              return feibo(num - 1, temp, res + temp)
    
    print(feibo(10,0,1))
    
    # 直接递归  尾递归 与 循环 的对比
    
    import time
    
    
    def Fib_recursion(num):
        '''
        直接使用递归法求解斐波那契数量的第num个数字
        '''
        if num < 2:
            return num
        return Fib_recursion(num - 1) + Fib_recursion(num - 2)
    
    
    def Fib_tail_recursion(num, res, temp):
        '''
        使用尾递归法求解斐波那契数量的第num个数字
        '''
        if num == 0:
            return res
        else:
            return Fib_tail_recursion(num - 1, temp, res + temp)
    
    
    def Fib_circle(num):
        '''
        直接使用循环来求解
        '''
        a = 0
        b = 1
        for i in range(1, num):
            c = a + b
            a = b
            b = c
        return c
    
    
    if __name__ == '__main__':
        num_list = [5, 10, 20, 30, 40, 50]
        for num in num_list:
            start_time = time.time()
            print(Fib_recursion(num))
            end_time = time.time()
            print(Fib_tail_recursion(num, 0, 1))
            end_time2 = time.time()
            print(Fib_circle(num))
            end_time3 = time.time()
            print('正在求解的斐波那契数字下标为%s' % num)
            print('直接递归耗时为 :', end_time - start_time)
            print('尾递归调用耗时为:', end_time2 - end_time)
            print('直接使用循环耗时为:', end_time3 - end_time2)
    

    递归练习题

    >>>打印f-e的数:
    
    def pri(f, e):
        if f > e:
            return
        else:
            print(f)
            return pri(f + 1, e)
    
    
    pri(1, 6)
    
    
    >>>求一个列表的和:
    def sum_lis(li, f):  # 如果单独是传入一个列表,它体现不了变化
        """
        :param li: 传入一个列表
        :param f: 列表起始位置
        :return: 列表和
        """
        if f == len(li) - 1:  # 表示起始位置也是结束位置,即只有一个元素
            return li[f]
    
        return li[f] + sum_lis(li, f + 1)
    
    
    print(sum_lis([1, 2, 3, 4, 5], 0))
    
    # 多引入一个 变化的参数,可以想到第一个元素加上剩下的元素,规模不断变小
    
    # 需求:求 1+2+3+4........100 的和
    num = 1
    count = 0
    while num <= 100:
        count += num
        num += 1
    print(count)
    
    '''
    思路:
    sum(1) + 2 +3.....100
    sum(2) + 3........100
    sum(3) + 4........100
    ...
    sum(98)+99+100
    sum(99) + 100
    sum(100)
    
    sum(100) = sum(99) + 100
    sum(99) = sum(98) + 99
    sum(98) = sum(97) + 98
    .....
    
    sum(2) = sum(1) + 2
    
    sum(1) = 1
    '''
    # 用递归函数解决
    def sum(num):
        if num == 1:  # 出口
            return 1
        return num + sum(num - 1)  # 一直返回sum(num-1)+num,每次递归调用,有return才能有返回值
    
    
    print(sum(100))
    
    >>>需求:打印斐波那契数列
    def fibo(num):  # 参数是表示第n个斐波那契数,函数整体表示获取斐波那契数列中第n个数字的值
        if num == 1 or num == 2:  # 第一个和第二个都是1
            return 1  # 返回1,出口
        return fibo(num - 1) + fibo(num - 2)  # 规律,后一项加上后两项,就等于斐波那契数列第n个数字的值
    
    
    if __name__ == '__main__':
        list_num = []  # 创建一个空列表,开始
        for i in range(1, 21):  # 遍历1-20
            list_num.append(fibo(i))  # 注意这里开始调用函数,获得一个斐波那契数字,将获取到的值填充到list_num
        print(list_num)
    
    
    # 最佳解法:
    def fei_bo(n):
        if n <= 1:
            return (n, 0)
        else:
            (a, b) = fei_bo(n - 1)
            return (a + b, a)
    
    
    print(fei_bo(5))
    # 这里是线性的解法,不再重复计算前一项已知的数
    
    # 求最大公约数
    def maxg(m, n):
        if n == 0:
            return m
        return maxg(n, m % n)
    
    
    print(maxg(6, 0))
    
    # 最大公约数:
    # 如果m%n=0 则n是m的最大公约数;例如4%2=0 则2是最大公约数 
    # 如果m%n=K 则 n%k=?0 >>> f(m,n)=f(n,m%n)
    
    
    >>>用递归实现列表排序:
    def ins(li, k):
        if k == 0:
            return
        # 对前K个元素进行排序
        ins(li, k - 1)
        # 把位置K的元素插入到前面的部分
        x = li[k]
        index = k - 1
        while x < li[index]:
            li[index + 1] = li[index]
            index -= 1
        li[index + 1] = x
        print(li)
    
    
    ins([1, 4, 3, 2], 3)
    
    >>>需求:递归实现遍历目录
    
    import os
    
    
    def get_alldirfile(source_path):  # 定义一个函数获取用户输入的路径名下所有目录和文件
        if not os.path.exists(source_path):  # 判断用户输入的目录是否存在
            return  # 不存在,直接返回,结束该函数,找到一个出口
        list_name = os.listdir(source_path)  # lisdir获取所有目录,并全部放到一个列表中
        for flie_dirname in list_name:  # 遍历下所有的文件目录名
            abs_path = os.path.join(source_path, flie_dirname)  # 拼接成绝对路径
            # 判断下一级是否是目录还是文件,是文件结束,是目录继续深入,直到是文件结束
            if os.path.isfile(abs_path):  # 是文件
                print("file_path:%s" % (abs_path))
            # 也可进行复制操作,open(abs_path,"w",encoding="utf-8")
            if os.path.isdir(abs_path):
                get_alldirfile(abs_path)  # 递归函数
    
    
    if __name__ == '__main__':
        path = r"F:\日语\快乐50音"
        get_alldirfile(path)
    
    # 优化
    import os
    
    
    def file_get(file_path, n):
        list_file = os.listdir(file_path)
        for file in list_file:
            abs_file = os.path.join(file_path, file)
            if os.path.isdir(abs_file):
                print("\t" * n, file)
                file_get(abs_file, n + 1)
            else:
                print("\t" * n, file)
    
    
    file_get("D:\KuGou", 1)
    
    展开全文
  • 递归九讲2021 7-9.zip

    2021-08-22 15:00:18
    递归九讲2021 7-9.zip
  • 递归九讲2021 2-6.zip

    2021-08-22 15:02:55
    递归九讲2021 2-6.zip
  • 什么是递归,通过这篇文章,让你彻底搞懂递归

    万次阅读 多人点赞 2020-08-10 10:40:50
    递归之前先看一下什么叫递归递归,就是在运行的过程中调用自己。 构成递归需具备的条件: 1. 子问题须与原始问题为同样的事,且更为简单; 2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。 递归...
  • 递归详解——让你真正明白递归的含义

    千次阅读 多人点赞 2021-08-25 13:52:12
    让天下没有难学的程序(只有秃头的程序员 2333),学会程序和算法,走遍天下都不怕!...可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,..
  • 二叉树非递归求叶子节点,以及前序、中序、后序遍历算法
  • 用例子理解递归

    千次阅读 多人点赞 2020-11-08 21:47:01
    在说什么是递归之前,我想屏幕前的你应该会使用循环来解决一些问题了。那循环又是什么呢?循环是指在程序中需要反复执行某个功能而设置的一种程序结构。它由循环体中的条件,判断继续执行某个功能还是退出循环。 &...
  • 动画:这一次用动画搞懂递归

    千次阅读 多人点赞 2020-03-23 18:53:55
    递归这玩意儿,尤其是对于初学者,在数据结构和算法中归为“玄学”一类。咳咳,如果今天鹿哥能把这玄学的玩意儿讲明白,岂不是要上天。同样讲不明白的后果,鹿哥将会被后台的石锤大队石锤… 其实不学递归也没啥,...
  • Java中的递归详解

    千次阅读 2022-04-27 12:55:38
    概述 递归累加求和 计算1 ~ n的和 代码执行图解 递归求阶乘 递归打印多级目录 综合案例 文件搜索 文件过滤器优化 Lambda优化
  • 15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,543,158
精华内容 617,263
关键字:

递归

友情链接: STM32F107_SSL.rar