第5章递归 5.1什么是递归 提纲 5.2递归算法的设计 CONTENTS 作业 上机实验题 1/66
CONTENTS 提纲 1/66
什么是递归5.1递归的定义5.1.1在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数A调用过程或函数B，而B又调用A，称之为间接递归。在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所以主要讨论直接递归。如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，称为尾递归。2/66
在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。 若调用自身，称之为直接递归。 若过程或函数A调用过程或函数B，而B又调用A，称之为间接递归。 在算法设计中，任何间接递归算法都可以转换为直接递归算法来实现，所 以主要讨论直接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，称为 尾递归。 2/66
【例5.1】以下是求n！（n为正整数）的递归函数。它属于什么类型的递归。int fun(int n)//语旬1(if(n==1)1/语句2return(1);//语旬3else//语句4return(fun(n-1)*n);解：直接递归函数。又由于递归调用是最后一条语句，所以它又属于尾递归。3/66
【例5.1】以下是求n!（n为正整数）的递归函数。它属于什么类型的递归。 int fun(int n) { if (n==1) //语句1 return(1); //语句2 else //语句3 return(fun(n-1)*n); //语句4 } 解：直接递归函数。又由于递归调用是最后一条语句，所以它 又属于尾递归。 3/66
递归算法通常通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解。递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了算法的代码量。原问题小问题1小问题1小问题K4/66
递归算法通常通常把一个大的复杂问题层层转化为一个或多个与原问题 相似的规模较小的问题来求解。 递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算， 大大减少了算法的代码量。 原问题 小问题1 小问题1 . 小问题k 4/66
一般来说，能够用递归解决的问题应该满足以下3个条件：需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。递归调用的次数必须是有限的。必须有结束递归的条件来终止递归。5/66
一般来说，能够用递归解决的问题应该满足以下3个条件： 需要解决的问题可以转化为一个或多个子问题来求解，而这些子 问题的求解方法与原问题完全相同，只是在数量规模上不同。 递归调用的次数必须是有限的。 必须有结束递归的条件来终止递归。 5/66