5.2.2 递归 课件-2021-2022学年浙教版（2019）高中信息技术选修1

5.2.2 递归 大问题的解决中嵌套着与 原问题相似的规模较小的 问题。 这种解决问题的方式在计 算机科学中称为递归，通 过函数自己调用自己来实 现，即一个函数在其定义 中直接或间接调用自身的 一种方法。 在数据结构与算法设计中，递归十分有用，它往往能使函数的定义和算法 的描述简洁且易于理解，极大地减少程序代码量。如前面学过的的二叉树， 由于其本身固有的递归特性，特别适合用递归的形式来描述。 能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将 它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的 解，并且这些规模较小的问题也能采用同样的分解和综合方法。 当递归到达某个边界，如问题规模缩减为0或1时，能直接得解。因此，在设 计递归算法时，要满足两个条件：确定递归公式和递归结束条件。 例：利用递归算法求n的阶乘（n!=1*2*…*n）。由数学知识可知，n阶乘 的递归定义为：它等于n乘以n-1的阶乘，即n!=n*(n-1)!，并且规定0!=1。 设函数fac(n)=n!，则fac(n)可表示为： fac(n)= 1 (n=0) n*fac(n-1) (n>0) 按照这个公式，可以将求n!的问题转化成求(n-1)!的问题；而求(n-1)!的问题， 又可以转化成求(n-2)!的问题；求（n-2）!的问题，又可以转化成求(n-3)！的 问题，如此继续，直到最后转化成求0！的问题。再反过来，依次求出1！， 2！，…，直到最后求出n!。因此，在该问题中，递归公式是 fac(n)=n*fac(n-1),当n=0时递归结束。 求n的阶乘的相应的程序及测试结果如下： def fac(n): if n==0: s=1 else: s=n*fac(n-1) return s print(fac(3)) 当主程序执行函数fac(3)时，引起第1次函数调用，进入函数后， 参数n=3，应执行计算3*fac(2)。直到计算fac(0)，将引起对函数fac的 第4次调用。 以上调用的执行和返回情况，如下图所示。 fac(3) 3*fac(2) 第1次调用 第2次调用 2*fac(1) 第3次调用 1*fac(0) 第4次调用 1 递归调用