第十一讲函数的递归调用及函数中的变量定义
第十一讲函数的递归调用及函数中的变量定义
一、函数的递归调用
1．递归的概念
直接递归调用：调用函数的过程中又调用该函数本身，自己调用自己。
间接递归调用：调用f1函数的过程中调用f2函数，而f2中又需要调用f1。
以上均为无终止递归调用。为了让这种调用终止，一般要用if语句来控制使递归过程到某一条件满足时结束。
2、递归法
类似于数学证明中的反推法，从后一结果与前一结果的关系中寻其规律性。
递归法：从结果出发，归纳出后一结果与前一结果直到初值为止存在的关系
编程思想：设计一个函数（递归函数），这个函数不断使用下一级值调用自身，直到结果已知处——选择控制结构
其一般形式是：
递归函数名f （参数n）
{ if (n=初值)
结果=常量；
else
结果=含f(x-1)的表达式；
return 结果；
}
例1．输入一个n,编写函数求n!，根据不同的算法，我们可以用三种方式。
方式一：用递推算法，Sn=n!的递推关系如下：
1 （n=1,0）
Sn=
Sn-1×n n>1
是一种累计乘积的关系，先得到上一个数的阶乘，然后再得到得到下个数的阶乘，用循环结构来实现。
程序代码如下：
main()
{ int n;
float sn;
float fac(int ); /*函数的声明*/
printf("Input n=");
scanf("%d",&n);
sn=fac(n); /*函数的调用*/
printf("%d!=%.0f",n,sn);
}
float fac(int n) /*函数的定义*/
{ float f=1.0;
int i;
if (n==0||n==1) return f;
for(i=1;i<=n;i++)
f=f*i;
return f;
}
方式二：用递归算法，f(n)=n!的递归求解关系如下：
1 （n=1,0）
f(n)=
f(n-1)×n n>1
递归程序分两个阶段执行——
①回推（调用）：欲求n! →先求 (n-1)! →(n-2)! →…→ 1!
若1！已知，回推结束。
②递推（回代）：知道1！→2！可求出→3！→…→ n！
注意：在此可画图来说明
程序清单如下：
main()
{ int n;
float sn;
float fac(); /*函数的声明*/
clrscr();
printf("Input n=");
scanf("%d",&n);
sn=fac(n); /*函数的调用*/
printf("%d!=%.0f",n,sn);
}
float fac(int n) /*函数的定义*/
{ float f;
if (n==0||n==1) f=1;
else f=fac(n-1)*n;
return f;
}
方法三：在函数中定义静态变量来实现，一般说来，在任何函数中，我们都可以定义变量：float f;而这种定义默认为f为自动变量atuo，当函数调用结束的时候，该变量的存储空间被释放，也就是说变量f不复存在。但如果我们在定义变量的时候，声明是静态变量：static float f；f的值在函数调用结束以后，占用的存储空间不被释放，下次调用时候，其初值就是上次调用结束的值，利用这一特性，我们可以用来解决阶乘的问题。
main()
{ int n,i;
float fac(); /*函数的声明*/
printf("Input n=");
scanf("%d",&n);
for(i=1; i<=n;i++) /*函数的循环调用*/
printf(“%d!=%f\n”,i,fac(i));
}
float fac(int n) /*函数的定义*/
{ static float f=1;
if n>0
f=f*n;
return f;
}
例2 在屏幕上显示杨辉三角形,行数由用户输入。
分析：若起始行为第1行，则：第x行有x个值，对第x行第y列，
其值（不计左侧空格时）为以下递归关系：
1 （y=1|| y=x）
c(x,y)=
c(x-1,y-1)+c(x-1,y)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
………………
程序如下:
main(){
int i,j,n;
printf("Input n=");
scanf("%d",&n);
for (i=1;i<=n;i++)
{ for (j=0;j<=n-i;j++)
printf(" "); /*为了保持三角形态，此处输出两个空格*/
for (j=1;j<=i;j++)
printf("%3d ",c(i,j));
printf("\n");
}
}
int c(int x,int y)
{int z;
if (y==1||y==x) return 1;
else
{ z=c(x-1,y-1)+c(x-1,y);
return z;
}
}
作业题1：用递归算法计算Fibonacci数列问题。输入一个n,输出前n 项的和
1 (n=1)
提示：fib(n)= 1 (n=2)
fib(n-1)+fib(n-2) (n>1)
例三．运行下列程序，当输入字符序列AB$CDE并回车时，程序的输出结果是什么？
编程递归函数
#include
void rev()
{ char c;
c=getchar();
if (c=='$') printf("%c",c);
else
{ rev();
printf("%c",c);
}
}
main()
{
rev();
}
结果：$BA
思考题目：输入一个整数，将其转换为字符输出。。
二、变量的存储类别
存储类别：
●register型（寄存器型）
变量值存放在运算器的寄存器中——存取速度快，一般只允许2-3个，且限于char型和int型，通常用于循环变量（在微机的Turbo C中实际上自动转为auto型）。
●auto型（自动变量型）
变量值存放在主存储器的动态存储区（堆栈方式）。
优点——同一内存区可被不同变量反复使用
在函数中定义以上两个类型的变量以后，只能属于该函数，函数的调用结束时，变量的存
储空间便被释放，不能被保存下来。下次调用时，又给
变量重新分配存储空间。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。