(
课件网) 三、 递归算法及其应用 第五章 数据结构与算法 知识过关 (一)递归算法 1. 递归算法的概念 为求解规模为n的问题,设法将它分解成规模较小的问题,然后从这些小问题的解中方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,这种解决问题的方式在计算机科学中称为递归。当递归到达某个边界时,能直接得解。 递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小的问题又变成规模更小的问题,当问题小到一定程度时,可以直接得出它的解,从而得到原来问题的解。 2. 利用递归算法解决问题的关键步骤 (1)抽象建立递归模型,确定递归公式。 (2)确定临界条件(即递归结束条件)。 例如,下面的自定义函数f调用自身,因此属于递归算法,用自定义函数实现,也称为递归函数。 def f(n): #自定义函数f if n == 1: s = 1 else: s = n * f(n － 1)+ 1 #函数调用自身,属于递归调用 return s #返回函数值s k=int(input()) #主程序 print(f(k)) #调用函数f 3. 递归算法的实现要点 递归调用必须是有限的。进行算法描述时,必须设置相关的控制条件,使其成为有限的。这可以通过条件语句来实现,即只有在设定的条件成立时递归才继续,否则终止递归。可见,构成递归必须满足以下条件: (1)有明确的结束递归的边界条件(又称终止条件)以及结束时的边界值。 (2)函数的描述中包含其本身,即能用递归形式表示,且递归终止条件明确。 4. 递归算法的设计方法 当所求解的问题难于直接求解时,首先,把问题分解成若干个难度较小、较容易求解的子问题,子问题与原问题具有类同的结构。若子问题能够直接求解,则解之;如果子问题仍不能直接求解,将每个子问题再分解成若干个更简单的子问题,直到分解出的子问题能够很容易地求解或解已知,这是实现递归的模板。然后,设计递归出口(即结束递归的边界条件),当满足出口条件时,递归函数不能再调用自己,必须返回一个确定的值。 (二)迭代和递归的联系和区别 1. 递归 程序调用自身的编程技巧称为递归,是函数自己调用自己。由于递归会引起一系列的函数调用,并且有可能会有一系列的重复计算,递归算法的执行效率相对较低。 2. 迭代 迭代是利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话,那么迭代就是A不停地调用B。 理论上,迭代和递归在时间复杂度方面是等价的(不考虑函数调用开销和函数调用产生的堆栈开销),但实际上递归效率比迭代低,由于递归需要系统堆栈,所以空间消耗要比非递归代码大很多。 一般情况下,递归算法都可以转换为迭代算法。递归中一定有迭代,但是迭代中不一定有递归,大部分递归和迭代可以相互转换。递归的优点是易理解、容易编程,缺点是递归带来了大量的函数调用,导致效率较低。迭代虽然相对于递归效率高,但缺点是不容易理解,编写复杂问题时比较困难。 典例精选 【例1】 (2023·浙江1月选考)定义如下函数: def f(n): if n<3: return n return f(n－1)+f(n－3) 执行语句v=f(5),函数f被调用的次数是( ) A. 1 B. 5 C. 7 D. 15 【解析】 本题考查递归算法知识。观察自定义函数可知,当参数n大于等于3时,继续两次递归调用(参数为n－1和n－3),反之结束递归直接返回值。题干执行的语句中参数值为5较小,故可以直接模拟并分析计算过程:①f(5)=f(4)+f(2),调用函数f两次;②f(4)=f(3)+f(1),调用函数f两次;③f(3)=f(2)+f(0),调用函数f两次;再加上v=f(5)本身调用的一次,得到答案7。C正确。 C 【例2】 阶乘n!=1×2×3×…×n,利用递归思想可以转化为n!=(n ... ...
