数据结构与算法分析论文(递归的讨论)

数据结构与算法分析论文递归算法的讨论学号1415211013姓名李莉姗班级14电子1班华侨大学电子工程系递归算法的讨论所谓递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1)递归就是在过程或函数里调用自身。(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。(4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。下面就让我们结合例子详细讨论一下递归算法。一、递归算法的原理递归算法简单的说就是在函数中调用函数自身，不断调用，直到满足函数得出计算结果(某个条件)。因为其需要不断循环的调用自身，所以称为递归调用。递归的原理,其实就是一个栈(stack),比如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4又要是到3的,以此类推,所以递归式就先把5的阶乘表示入栈,在把4的入栈,直到最后一个,之后呢在从1开始出栈,看起来很麻烦,确实很麻烦,他的好处就是写起代码来,十分的快,而且代码简洁,其他就没什么好处了,运行效率出奇的慢。还有一个十分形象的例子：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事……如此循环往复到最终的要求。递归分为2种，直接递归和间接递归。直接递归，比如方法A内部调用方法A自身。间接递归，比如方法A内部调用方法B，方法B内部调用方法C，方法C内部调用方法A。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。递归的三个条件：边界条件、递归前进段、递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。二、递归算法的用处了解了递归算法的原理，那么什么时候需要用到递归算法呢？①问题的定义是递归的。有许多数学公式、数列的定义是递归的，例如求n!和Fibonacci数列等。这些问题的求解的过程可以将其递归定义直接转化为对应的递归算法。例如阶乘函数的定义1当n=0时n！=n*(n-1)*…*1当n0时这时候递归的定义可以用如下的函数表示：1当n=0时f(n)=n*f(n-1)当n0时也就是说，函数f(n)的定义用到了自己本身f(n－1)。②数据结构是递归的。有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LinkList;该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下：intSum(LinkList*head){if(head==NULL)return0;elsereturn(head-data+Sum(head-next));}③问题求解的过程是递归的。一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法。有序数组元素为1；3；4;5;17;18;31;33;寻找值为17的数据（如上图）。折半查找无非就是三种情况，其中两种情况的问题解法如果以算法来表示，都存在算法调用自身的情况。递归算法的特点就是：将问题分解成为形式上更加简单的子问题来进行求解。递归算法不但是一种有效的分析问题方法，也是一种有效的算法设计方法，是解决很多复杂问题的重要方法。递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。利用递归算法解题，首先要对问题的以下三个方面进行分析：1、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。2、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。3、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。把以上三个方面分析好之后，就可以在子程序中定义递归调用。三、递归算法的一个坏例子汉诺塔(Hanoitower)问题：传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规则：第一，一次只能移动一个金盘。第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。第三，任何时候都不能把大的金盘放在小的金盘上。神话说，如果僧人把64个金盘完全地从一根宝石柱移到了另外一根上，传说中的末日就要到了——世界将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。移动金盘是个很繁琐的过程。通过计算，对于64个金盘至少需要移动2的64次方，等于1.8乘以10的19次方。如果僧侣移动金盘一次需要1秒钟，移动这么多次共需约5845亿年。把这个寓言和现代科学推测对比一下倒是有意思的。按照现代的宇宙进化论，恒星、太阳、行星（包括地球）是在三十亿年前由不定形物质形成的。我们还知道，给恒星特别是给太阳提供能量的“原子燃料”还能维持100～150亿年。因此，我们太阳系的整个寿命无疑要短于二百亿年。可见远不等僧侣们完成任务，地球早已毁灭了。下面先试验一下汉诺塔游戏，体会一下它的原理，思考其中的递归思想。可以用递归方法求解n个盘子的汉诺塔问题。基本思想：1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱借助C移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再借助A移到C柱。（如下图）下面进行汉诺塔递归程序设计。首先，盘子的个数n是必须的一个输入参数，对n个盘子,我们可从上至下依次编号为1,2,…,n；其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg，auxPeg和toPeg；最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：将第i个盘子从X移动到Y。移动方法示意图如下这样，汉诺塔问题的递归算法可设计如下：voidHanoi(intn,chara,charb,charc){if(n==1)//递归出口printf(\t将第%d个盘片从%c移动到%c\n,n,a,c);else{Hanoi(n-1,a,c,b);//把n-1个圆盘从fromPeg借助toPeg移到auxPegprintf(\t将第%d个盘片从%c移动到%c\n,n,a,c);Hanoi(n-1,b,a,c);//把n-1个圆盘从auxPeg借助fromPeg移到toPeg}}主程序如下：#includestdio.hvoidmain(){intn;//汉诺塔盘子数目printf(\n请输入汉诺塔盘子数目:\n);scanf(%d,&n);getchar();printf(%d个盘片移动过程:\n,n);Hanoi(n,'A','B','C');getchar();return;}程序运行截图如上当盘子数字比较小时运行时间较短，可以接受。但是当盘子数字≥20时，程序运行时间长到无法忍受。究其原因，我们用时间复杂度来分析。在算法分析中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解。实际上，这个问题是数学上求解渐近阶的问题。经过计算，上面程序的时间复杂度为O(2expn)。可见，当盘子数上升时，运算消耗的时间呈指数态上升。所以当盘子数多的时候，计算机需要消耗很久才能算出结果，而这个时间往往让人不可忍受。用递归算法实现的汉诺塔程序效率分析总结如下：优点：①递归过程结构清晰②程序易读③正确性容易证明缺点：①时间效率低②空间开销大，问题规模扩大时，噩梦来临。③算法不容易优化所以，对于频繁使用的算法，或不具备递归功能的程序设计语言，需要把递归算法转换为非递归算法。而采用迭代算法、尾递归的消除、利用栈消除任何递归就是3个常用的递归算法的非递归化处理方法。至于这三个方法这里就不赘述了，需要了解的可以查阅相关书籍资料。参考文献1.《数据结构与算法分析——C语言描述》MarkAllenWeiss著2.《C语言设计语言》DennisM.Ritchie和BrianW.Kernighan合著3.百度百科baike.baidu.com