当前位置：首页 > news >正文

C语言程序设计P5-3【应用函数进行程序设计 | 第三节】——知识要点：函数的嵌套调用和递归调用

news 来源：原创 2025/1/17 23:30:11

知识要点：函数的嵌套调用和递归调用

视频

一、任务分析

二、必备知识与理论

三、任务实施

一、任务分析

本任务要求用递归法求 n!。

我们知道n!=n×(n-1)×(n-2)×……×1=n(n-1)!递归公式为：

1.上面公式分解为n!=n×(n-1)!，即将求n!的问题变为求(n-1)!的问题，(n-1)!= (n-1)×(n-2)!，即将求(n-1)!的问题变为求(n-2)!的问题，再将求(n-2)!的问题变为求(n-3)!的问题，依此类推，直到最后成为求0!，这是递推过程；

2.反过来求0!=1，1!，2!，3!，……，n!，为“回归过程”。

二、必备知识与理论

1．函数的嵌套调用

在C语言中，函数定义都是互相平行、独立的模块，无隶属关系，只存在调用和被调用的关系，除了主函数不能被其他函数调用外，其它函数之间都可以互相调用。

【例5.4】写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果。

算法分析：在数学上，两数的最小公倍数=两数乘积/两数的最大公约数。

求两个数的最大公约数应用辗转相除法：已知两个整数M和N，假定M>N，则求M%N，若余数r为0，则N即为所求；若余数r不为0，用N除r，再求其余数……直到余数为0，则除数就是M和N的最大公约数。

程序代码如下：

#include <stdio.h>int gcd(int a,int b)  /* 求最大公约数——辗转相除法 */{ int r,t;if(a<b){t=a;a=b;b=t;}r=a%b;while(r!=0){a=b;b=r;r=a%b; }return (b);}int lcm(int a,int b)   /* 求最小公倍数 */{int r;r=gcd(a,b);return(a*b/r);}main()   /* 主函数 */{int x,y; printf("please input two numbers:\n"); scanf("%d,%d",&x,&y); printf("%d\n",gcd(x,y));printf("%d\n",lcm(x,y));}

运行结果：

please input two numbers:

66,78↙

858

在这个例子中，主函数首先调用了函数gcd()求最大公约数，然后调用函数lcm()求最小公倍数，而在函数lcm()中又调用了函数gcd()，这就是一个函数嵌套调用的过程。

注意：①函数之间没有从属关系，一个函数可以被其它函数调用，同时该函数也可以调用其它函数。

②在C语言中，函数可以嵌套调用，但不可以嵌套定义。

2．函数的递归调用

函数的递归调用实际上是函数嵌套调用的一种特殊情况。在调用一个函数的过程中直接或间接地调用该函数本身，称为函数的递归调用。直接调用称为直接递归调用，间接调用称为间接递归调用。程序中常用的是直接递归。将这种在函数体内调用该函数本身的函数称为递归函数。

三、任务实施

用递归的方法求n!

我们知道n!=n×(n-1)×(n-2)×……×1=n(n-1)!递归公式为：

算法分析：

(1)上面公式分解为n!=n×(n-1)!，即将求n!的问题变为求(n-1)!的问题，(n-1)!= (n-1)×(n-2)!，即将求(n-1)!的问题变为求(n-2)!的问题，再将求(n-2)!的问题变为求(n-3)!的问题，依此类推，直到最后成为求0!，这是递推过程；

(2)反过来求0!=1，1!，2!，3!，……，n!，为“回归过程”。

(3)以求4的阶乘为例，4!=4×3!，3! =3×2!，2!=2×1!，1!=1，0!=1，它的递归结束条件是当n=1或n=0时，n!=1。

#include <stdio.h>float fac(n){ float f;if(n<0) printf("n<0,data error\n");else if(n==0||n==1) f=1;else f=fac(n-1)*n;   /* 递归调用 */return(f);}main(){int n;float y;printf("input an integer number:");scanf("%d",&n);y=fac(n);    /* 调用递归函数 */printf("%d!=%10.0f\n",n,y);}

运行情况如下：

input an integer number:4↙

4!= 24

递归过程分为两个阶段，第一阶段是“回推”阶段，即将求解4!变成求解4×3!，3!变成求解3×2!……直到1!=1为止；第二阶段是“递推”阶段，即根据2×1!得到2!，再根据3×2!得到3!，4×3!得到4!，结果为24。显然，在一个递归过程中，回推阶段是有限的递归调用过程，这样就必须要有递归结束条件，否则会无限地递归调用下去。

本例的递归结束条件为：当n的值为0或为1时，fac(n)的值为1； n<0时，作为错误输入数据。

在递推阶段中，函数执行完后必定要返回主调函数，通过return语句将fac(n)的值带回到上一层fac(n)函数，一层一层返回，最终在主函数中得到fac(4)的结果。

注意：一个合法的递归应该由两部分构成，一是递推公式，二是结束条件，缺少任何一个都无法利用递归解决问题。

最后对递归函数作如下概括：

(1)有些问题既可以用递归的方法解决，也可以用递推的方法解决。有些问题不用递归是难以得到结果的，如汉诺塔。某些问题，特别是与人工智能有关的问题，本质上是递归的。

(2)递归函数算法清晰，代码简练。如汉诺塔问题可谓复杂，程序却极为简单。

(3)从理论上讲，递归函数似乎很复杂，其实它是编程中一类问题的算法，最为直接。一旦熟悉了递归，它就是处理这类问题的最清晰的方法。

(4)C编译系统对递归函数的自调用次数没有限制，但当递归层次过多时，可能会引起内存不足而造成运行出错，尤其是函数内部定义较多的变量和较大的数组时。

(5)函数递归调用时，在栈上为局部变量和形参分配存储空间，并从头执行函数代码。递归调用并不复制函数代码，只是重新分配相应的变量，返回时再释放存储空间。递归需要保存变量、断点、进栈、出栈，增加许多额外的开销，会降低程序的运行效率，所以程序设计中又有一个递归消除的问题。

一、任务分析

二、必备知识与理论

三、任务实施

相关文章：