高中二年级下学期信息科技《递归结构》教学课件

5.1迭代与递归5.1.2递归5.1.2递归1、递归的基本概念若一个对象用自己来定义自己或部分地包含自己，则称这个对象是递归的。若一个过程直接地或间接地调用自己，则称这个过程是递归过程。对于程序设计而言：

函数直接调用函数本身，称为直接递归调用；

在函数中调用其他函数，其他函数又调用原函数，构成了函数自身的间接调用，则成为间接递归调用。5.1.2递归2、递归在数学中的应用通过函数的递归调用，可以用于解决数学中给出初值和递推关系的数列问题。例3：阶乘数列由这样一组数组成：1,2,6,24,120,720,...，阶乘公式可以表示为n!=n*(n-1)*(n-2)*...*1，如何使用程序求解n!的值？阶乘数列的通项公式并不明显，而其求解过程与求和s=1+2+3+...+n类似，同样包含重复性的动作，因此也可以使用迭代法进行求解。5.1.2递归2、递归在数学中的应用例3：阶乘数列由这样一组数组成：1,2,6,24,120,720,...，阶乘公式可以表示为n!=n*(n-1)*(n-2)*...*1，如何使用程序求解n!的值？方法一：迭代法。 intn,s=1; //初始化阶乘的值s cin>>n; //输入n的值 for(inti=1;i<=n;i++) { s=s*i; //将数字i累乘进s中。 }5.1.2递归2、递归在数学中的应用例3：阶乘数列由这样一组数组成：1,2,6,24,120,720,...，阶乘公式可以表示为n!=n*(n-1)*(n-2)*...*1，如何使用程序求解n!的值？方法二：递归。

从另一个角度考虑，n!=n*(n-1)!。

因此，为了计算n!的值，可以先计算出(n-1)!的值，然后用其结果乘上n。

而为了计算(n-1)!的值，又需要计算(n-2)!的值，然后与(n-1)相乘。

以此类推，问题由大化小，始终执行重复性的动作，因此可以使用函数来嵌套实现。

5.1.2递归2、递归在数学中的应用例3：阶乘数列由这样一组数组成：1,2,6,24,120,720,...，阶乘公式可以表示为n!=n*(n-1)*(n-2)*...*1，如何使用程序求解n!的值？方法二：递归。 intf(intn) //定义递归函数f(n)表示求解n!的值 { if(n==1)return1;//n=1时可以直接返回结果1!=1

returnn*f(n-1); //n>1时再次调用函数f自身计算子问题(n-1)! //并返回当前问题的结果n*(n-1)!。 }

5.1.2递归2、递归在数学中的应用以上述程序求解f(3)的过程为例：

为了计算f(3)的值，需要求出f(2)的值并乘上3。

不断递推直到问题规模缩小到易于计算的边界情况。

将结果通过函数值返回到调用它的上一层函数，并依次计算出新的结果。易于计算的边界情况即为函数递归调用应遵循的终止条件。5.1.2递归3、递归算法的思想与应用递归算法的思想：

为求解一个不能或不好直接求解的大问题，设法将其分解为规模较小但解法相同的小问题，并且这些小问题也能采用同样的分解方法再分解为规模更小的小问题，当规模最小的一个或几个值能直接得出解时，再利用这些小问题的解构造出大问题的解。5.1.2递归3、递归算法的思想与应用递归算法解决问题的特点：（1）终止条件：必须有明确的递归终止条件，否则程序将陷入无穷循环而无法终止。（2）规模缩小：子问题在规模上比原问题小，或更接近终止条件（3）模式相似：子问题可通过再次递归调用求解或因满足终止条件而直接求解（4）问题划分：子问题的解应能组合为整个问题的解。5.1.2递归3、递归算法的思想与应用递归算法适用的问题类型：（1）数据本身的定义是递归/递推定义。

例如数学上常用的阶乘数列、斐波那契数列、幂函数等（2）问题的答案可以由相似的子问题答案组合而成（3）数据的结构形式按递归定义。

如链表、树的遍历、图的搜索等。5.1.2递归3、递归算法的思想与应用例4：斐波那契数列(Fibonacci)，又称黄金分割数列，由这样一组数组成：1,1,2,3,5,8,13,21,34,55,89,144,233,...，使用程序求解斐波那契数列的第n项。观察该数列，可以发现数列中每一项等于前两项之和，满足递推关系。递推关系可以使用递归算法求解。为了求解第n项，需要求解第n-1项和第n-2项，因此可以使用函数递归调用。当n=1,2时可以直接计算，因此设置为终止条件。5.1.2递归3、递归算法的思想与应用例4：斐波那契数列(Fibonacci)，又称黄金分割数列，由这样一组数组成：1,1,2,3,5,8,13,21,34,55,89,144,233,...，使用程序求解斐波那契数列的第n项。 intfib(intn) //定义函数fib表示斐波那契数列的第