递归：-一种优雅的算法设计策略.pptx

1、递归：一种优雅的算法设计策略,化志章hzz,内容,递归在计算机科学中的作用递归：一种优雅的算法设计策略什么是递归递归程序的核心要素递归的执行机理递归算法设计综合示例回顾与总结,2,1.递归在计算机科学中的作用,计算机科学中的递归：递归算法设计递归数据结构递归函数论具体应用：编译器、语言、硬件结构,3,对特定算法程序，如汉诺塔等，递归解决方案：简单、优雅；非递归解决方案：复杂、晦涩,如：普通链表、树/二叉树等递归数据结构：动态、易于扩充；非递归数据结构：静态、难扩充；,递归函数论用另一种方式研究可计算性，与图灵可计算函数作用类似。可计算的，就是能用计算机求解的。,递归影响非常广泛，编译器有使用递

2、归的数据结构和算法，有专门的递归语言（函数式语言）、硬件中对栈的支持,本讲座讨论内容,2.递归：优雅的算法设计策略,什么是递归递归程序的核心要素递归程序的执行机理递归算法设计综合示例,4,2.1什么是递归,递归的常规定义子程序自己调用自己，或是若干子程序间的环状调用。如A()调用B()，B()调用C()，C()调用A()计算机科学百科全书陈火旺、贲可荣是将一个较大问题归约到一个或多个子问题的求解过程，这些子问题与原问题结构相同，但规模更小。,5,此定义仅刻画了递归程序调用的表象，对如何设计递归程序无帮助！,此定义从算法设计角度剖析递归，有助于设计递归程序。,2.2递归程序的核心要素,剖析递归定

3、义总策略：原问题分解为若干子问题限制：原问题与子问题要结构相同规模更小（即小至极限）：可简化求解！例如：求1到n的累加和总策略：sum(n)=sum(n-1)+n;小至极限：sum(0)=0;,6,递归是将一个较大问题归约到一个或多个子问题的求解过程，这些子问题与原问题结构相同，但规模更小。,2.2递归程序的核心要素,递归的核心要素递推关系：即原问题分解规则如：sum(n)=sum(n-1)+nifn0初始条件：即一步得解。如：sum(n)=0ifn=0注意：初始条件用于终止递推分解。错误的递归sum(n)=sum(n+1)-(n+1);ifn0sum(n)=0;ifn=0,7,递归是将一个较

4、大问题归约到一个或多个子问题的求解过程，这些子问题与原问题结构相同，但规模更小。,递推关系，就是把大问题分解成子问题的一种函数关系。它刻画的是问题如何分解。换言之，刻画如何根据子问题求解出原问题；,初始条件，就是问题的最简单状态，可直接获得解。或者说是最小规模的子解。初始条件刻画了问题分解的尽头。,递归与数学归纳法相似：假定已知，求出未知。如，在求解sum(n)时，假定sum(n-1)已知，有sum(n)=sum(n-1)+n即假定已知子问题的解，求原问题的解。,2.3递归程序的执行机理,8,S(5)=S(4)+5,S(4)=S(3)+4,S(3)=S(2)+3,S(2)=S(1)+2,S(1

5、)=S(0)+1,S(5)=15,S(0)=0,sum(n)=sum(n-1)+nifn0sum(n)=0ifn=0,递归降解,迭代计算,2.4递归算法综合示例,1、打印数字三角2、斐波那契数列3、楼梯台阶走法问题4、数组查找问题5、中序+前序创建二叉树,9,2.4.1打印数字三角,10,原问题：打印数字三角分解：n行大三角=n-1行小三角+第n行初始条件当n2f(n)=1ifn=1或n=2,2.4.2斐波那契数列,12,拓展1：兔子3个月成熟，1月初引入，求第n月兔子数分解：假定f(n)=第n月的兔子总数，有f(n)=f(n-1)+第n月的新增兔子总数第n月新增兔子总数=第n月成熟兔子总数=

6、第n-3月兔子总数=f(n-3)即f(n)=f(n-1)+f(n-3)初始条件f(1)=1,f(2)=1；f(3)=1,2.4.2斐波那契数列,13,拓展2：兔子1个月成熟，成熟后每月繁殖1次，只能繁殖3次，1月初引入，求第n月兔子数分解：假定f(n)=第n月的兔子总数，有f(n)=f(n-1)+第n月新增兔子总数第n月新增兔子总数=第n-1月成熟总数-第n-1月绝育数目=f(n-2)-f(n-4)即f(n)=f(n-1)+f(n-2)-f(n-4)ifn4初始条件f(1)=1,f(2)=2；f(3)=3;f(4)=5,2.4.2斐波那契数列,14,拓展3：幼兔1个月成熟，成熟后每月繁殖1次，

7、只能繁殖3次，能活9个月，1月初引入1对，求第n月兔子数分解：假定f(n)=第n月的兔子总数，有f(n)=f(n-1)+f(n-2)-f(n-4)-第n-1月死亡数即f(n)=f(n-1)+f(n-2)-f(n-4)-f(n-9)ifn9初始条件f(1)=1;f(9)=26或f(14)、f(n)=f(n-1)+f(n-2)-f(n-4)if42,楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.,显然，上述两种走法没有重复，而且，再无第三种不同。,2.4.4数组查找问题,16,原问题：在a0.n-1中查找x分析：定义f(a,l,h,x)初始条件if(lh)

8、f(a,l,h,x)=-1if(al=x)f(a,l,h,x)=l递归降解if(al!=x)f(a,l,h,x)=f(a,l+1,h,x),给定元素x和数组a0n-1，若x在a中存在，返回其首次出现的位置；否则返回-1。,f(a,l,h,x)if(lh)return-1;if(al=x)returnl;returnf(a,l+1,h,x);,注：对查找类问题，初始条件定有两个，找到或找不到。通常将“基于空集的搜索”表示“找不到”。,2.4.5中序+前序创建二叉树,17,原问题：利用inn+pren创建二叉树定义creatBtree(in,pre)，令in中左子树序列为in.L，右子树序列为in

9、.R分析根bt：由pre确定；左右子树，由bt+in确定；,利用二叉树中序遍历序列in和前序遍历序列pre创建一棵二叉树。,creatBtree(in,pre)if(in=空集)returnNULLbt=prelow;bt-L=create(in.L,pre.L);bt-R=create(in.R,pre.R);returnbt;,creatBtree(pre,L1,h1,in,L2,h2),x,y,3.回顾与总结,18,递归思维是递归求解的关键递归思维，首要关心求解问题的整体性合理的假定子解是求解的关键递归描述的核心是递归降解规则和初始条件两要素的关系：重复使用递归降解规则，定能满足初始条件。递归思维，旨在构造求解问题的递归定义,单链表递归定义？typedefstructkkintdata;structkk*next;node;,单链表递归定义：1、只有头结点的链式结构是空的单链表；2、单链表尾部链接一个节点，还是单链表。,单链表的递归定义？,3.回顾与总结,19,关于初始条件初始条件刻画的是特殊的初始情形，一般不满足递归降解规律；如：斐波那契数列中兔子3个月成熟、10个月死亡等等；搜索类问题的初始条件，至少要要描述两种情况：