-
2021-05-26 01:52:42
线作业试卷列表
单选
1.以下叙述正确的是
分值:2
A. C语言中各函数之间既允许直接递归调用也允许间接递归调用
B. C语言中各函数之间既不允许直接递归调用也不允许间接递归调用
C. C语言中各函数之间既允许直接递归调用不允许间接递归调用
D. C语言中各函数之间既不允许直接递归调用允许间接递归调用
2.以下程序的输出结果是
char str[ ]="ABCD",*p=str;
printf ("%d ",*(p+4)); 分值:2
A. 68
B. 0
C. 字符D的地址
D. 不能确定的值
3.以下程序的输出结果是
main( )
{ int a[ ]={1,2,3,4 },i,x=0;
for(i=0; i<4; i++) { sub(a,&x); printf(“%d”, x); }
printf(“ ”);
}
sub( int *s, int *y)
{ static int t=3;
*y=s[t]; t-- ; } 分值:2
A. 1 2 3 4 B. 4 3 2 1
C. 0 0 0 0 D. 4 4 4 4
4.以下程序的输出结果是
main( )
{ int k=4, m=1,p;
p=func(k,m);
printf(“%d,”,p);
p=func(k,m);
printf(“%d ”,p);
}
func( int a, int b);
{ static int m, i=2;
i+=m+1;
m=i+a+b;
return(m);
} 分值:2
A. 8,17 B. 8,16
C. 8,20 D. 8,8
5.以下程序的输出结果是
void fun(int *s)
{ static int j=0;
do
s[j]+=s[j+1];
while(++j<2);
}
main( )
{ int k,a[10]={1,2,3,4,5};
for (k=1; k<3; k++) fun(a);
for (k=0; k<5; k++) printf(“%d”,a[k] );
} 分值:2
A. 34756
B. 23445
C. 35745
D. 12345
6.以下程序的输出结果是
f(int a)
{ int b=0;
static int c=3;
a=c ++, b ++;
return( a );
}
main( )
{ int a=2,i,k;
for(i=0 ; i<2; i++) k=f(a++);
printf(“%d ”,k);
} 分值:2
A. 3
B. 6
C. 5
D. 4
7.以下程序的输出结果是
int m=13;
int fun2(int x, int y)
{ int m=3;
return(x * y C m);
}
main( )
{ int a=7,b=5;
printf(“%d ”,fun2(a,b)/m ); } 分值:2
A. 1 B. 2
C. 7 D. 10
8.C语言中, 形参的缺省的存储类说明是
分值:2
A. auto ( 自动 )
B. static ( 静态 )
C. register ( 寄存器 )
D. extern ( 外部 )
9.以下选项中正确的整型常量是 __________。
分值:2
A. 12.
B. -20
C. 1,000
D. 4 5 6
10.以下选项中正确的实型常量是 __________。
分值:2
A. 0
B. 3.1415
C. 0.329*102
D. .871
11.以下选项中不正确的实型常量是__________。
分值:2
A. 2.607E-1 B. 0.8103e 2
C. -77.77 D. 456e-2
12.以下选项中不合法的用户标识符是_________。
分值:2
A. abc.c B. file
C. Main D. PRINTF
13.以下选项中不合法的用户标识符是__________。
分值:2
A. _123 B. printf
C. A$ D. Dim
14.C语言中运算对象必需是整型的运算符是__________。
分值:2
A. % B. /
C. ! D. **
15.可在C程序中用作用户标识符的一组标识符是_________。
分值:2
A. void define WORD
B. as_b3 _123 If
C. For -abc case
D. 2c DO SIG
16.若变量已正确定义并赋值,符合C语言语法的表达式是_________。
分值:2
A. a=a+7;
B. a=7+b+c,a++
C. int(12.3%4)
D. a=a+7=c+b
17.以下叙述中正确的是_________。
分值:2
A. a是实型变量,C允许进行以下赋值a=10,因此可以这样说:实型变量允许赋值整型值。
B. 在赋值表达式中,赋值号左边既可以是变量也可以是任意表达式。
C. 执行表达式a=b后,在内存中a 和 b存储单元中的原有值都将被改变,a的值已由原值改变为b 的值, b 的值由原值变为0。
D. 已有a=3,b=5。当执行了表达式 a=b ,b=a 之后,已使a 中的值为5,b 中的值为3。
18.以下叙述中正确的是________。
分值:2
A. 在C程序中无论整数还是实数,只要在允许的范围内都能准确无误的表示。
B. C程序由主函数组成。
C. C程序由函数组成。
D. C程序由函数和过程组成。
19.若a、b、c、d、都是int类型变量且初值为0,以下选项中不正确的赋值语句是_________。
分值:2
A. a=b=c=d=100; B. d++;
C. c+b; D. d=(c=22)-(b++);
20.以下合法的C语言赋值语句是_________。
分值:2
A. a=b=58 B. k=int(a+b);
C. a=58,b=58 D. --i;
21.若变量已正确说明为int类型,要给 分值:2
A. read(a,b,c);
B. scanf(“ %d%d%d” ,a,b,c);
C. scanf(“ %D%D%D” ,&a,%b,%c);
D. scanf(“ %d%d%d”,&a,&b,&c);
22.若变量已正确定义,要将a和b中的数进行交换,下面不正确的语句组是_________。
分值:2
A. a=a+b, b=a-b, a=a-b;
B. t=a, a=b, b=t;
C. a=t; t=b; b=a;
D. t=b; b=a; a=t;
23.若有以下程序段,c3中的值是__________。
int c1=1,c2=2,c3;
c3=c1/c2; 分值:2
A. 0 B. 1/2
C. 0.5 D. 1
24.若有以下程序段 ,其输出结果是__________。
int a=0,b=0,c=0;
c=(a-=a-5),(a=b,b+3);
printf(“ %d,%d,%d ”,a,b,c); 分值:2
A. 0,0,-10 B. 0,0,5
C. -10,3,-10 D. 3,0,-10
25.当运行以下程序时,在键盘上从第一列开始输入9876543210(此处代表Enter),则程序的输出结果是__________。
main( )
{ int a; float b,c;
scanf(“ %2d%3f%4f”,&a,&b,&c);
printf(“ a=%d,b=%f,c=%f ”,a,b,c);} 分值:2
A. a=98,b=765,c=4321
B. a=10,b=432,c=8765
C. a=98,b=765.000000,c=4321.000000
D. a=98,b=765.0,c=4321.0
26.若int类型占两个字节,则以下程序段的输出是__________。
int a=-1;
printf(“ %d,%u ”,a,a); 分值:2
A. -1,-1 B. -1,32767
C. -1,32768 D. -1,65535
27.以下程序段的输出是__________。
float a=3.1415;
Printf(“ |%6.0f| ”,a); 分值:2
A. |3.1415| B. | 3.0|
C. | 3| D. | 3.|
28.以下程序段的输出是__________。
float a=57.666;
pirntf(“ %010.2f ”,a); 分值:2
A. *0000057.66*
B. * 57.66*
C. *0000057.67*
D. * 57.67*
29.C语言中的简单类型有
分值:2
A. 整型,实型,逻辑型
B. 整型,实型,字符型
C. 整型,字符型,逻辑型
D. 整型,实型,逻辑型,字符型
30.C语言中,字符型(char)数据在微机内存中的存储形式是
分值:2
A. 反码 B. 补码
C. EBCDIC码 D. ASCII码
31.C语言中不合法的字符常量是
分值:2
A. ′\0XFF′ B. ‘\65′
C. ′&′ D. ′\028′
32.C语言中不合法的字符串常量是
分值:2
A. "121" B. ′Y=′
C. " " D. "ABCD\X6d"
33.判断char型变量C是否为大写字母的最简单且正确的表达式是
分值:2
A. ‘A ’<=C=‘Z’
B. (C>=′A′)&(C<=′Z′)
C. (′A′<=C)AND(′Z′>=C)
D. (C>=′A′)&&(C<=′Z′)
34.以下程序的输出结果是
main( )
{ char c1=′a′,c2=′y′;
printf("%d,%d ",c1,c2);
} 分值:2
A. 因输出格式不合法,无正确输出
B. 65,90
C. A,Y
D. 65,89
35.以下程序的输出结果是
main( )
{char x=′a′
x=(x>=′A′&& x<=′Z′)?(x+32):x;
printf("%c ",x);
} 分值:2
A. A B. a
C. Z D. z
36.以下各组选项中,均能正确定义二维实型数组a的选项是__________。
分值:2
A. float a[3][4];
float a[][4];
float a[3][]={{1},{0}};
B. float a(3,4);
float a[3][4];
float a[][]={{0},{0}};
C. float a[3][4];
static float a[][4]={{0},{0}};
auto float a[][4]={{0},{0},{0}};
D. float a[3][4];
float a[3][];
float a[][4];
37.以下正确的说法是__________。
分值:2
A. 实参和与其对应的形参占用独立的存储单元
B. 实参和与其对应的形参共占用一个存储单元
C. 只有当实参和与其对应的形参同名时才共占用一个存储单元
D. 形参是虚拟的,不占用存储单元
38.以下说法中正确的是
分值:2
A. C语言程序总是从第一个定义的函数开始执行
B. 在C语言程序中,要调用的函数必须在main函数中定义
C. C语言程序总是从main函数开始执行
D. C语言程序中的main函数必须放在程序的开始部分
39.以下函数的类型是
fff(float x){
printf("%d ",x*x);
} 分值:2
A. 与参数x的类型相同 B. void类型
C. int类型 D. 无法确定
40.以下程序的输出结果是
func(int a,int b)
{ int c
c=a+b;
return c; }
main( )
{ int x=6,y=7,z=8,r;
r=func((x--,y++,x+y),z--);
printf("%d ",r); } 分值:2
A. 11 B. 20
C. 21 D. 31
41.以下程序有错,错误原因是__________。
main()
{int *p,i;char *q,ch;
p=&i;
q=&ch;
*p=40;
*p=*q;
…
}
分值:2
A. p和q类型不一致,不能执行*p=*q;语句
B. *p中存放的是地址值,因此不能执行*p=40;语句
C. q没有指向具体的存储单元,所以*q没有实际意义
D. q虽然指向了具体的存储单元,但该单元中没有确定的值,所以不能执行*p=*q;语句
42.以下程序的输出结果是
double f(int n)
{ int i; double s;
s=1.0;
for(i=1; i<=n; i++) s+=1.0/i;
return s;
}
main()
{ int i,m=3; float a=0.0;
for(i=0; i
printf("%f ",a)L;
} 分值:2
A. 5.500000 B. 3.000000
C. 4.000000 D. 8.25
43.若有定义: int x,*pb;则在以下正确的赋值表达式是
分值:2
A. pb=&x B. pb=x
C. *pb=&x D. *pb=*x
44.以下程序的输出结果是
#include "stdio.h"
main()
{ printf("%d ",NULL); } 分值:2
A. 因变量无定义输出不定值
B. 0
C. -1
D. 1
45.有如下语句int a=10,b=20;*p1=&a,*p2=&b;如果让两个指针变量均指向b,正确的赋值方式是__________。
分值:2
A. *p1=*p2; B. p1=p2;
C. p1=*p2; D. *p1=*p2;
46.已知指针P的指向如图所示,则表达式*P++的值是
a[0] a[1] a[2] a[3] a[4]
10 20 30 40 50
P 分值:2
A. 20 B. 30
C. 21 D. 31
47.已知指针P的指向如图所示,则表达式* ++ P的值是
a[0] a[1] a[2] a[3] a[4]
10 20 30 40 50
P 分值:2
A. 20 B. 30
C. 21 D. 31
48.已知指针P的指向如图所示,则表达式++*P的值
a[0] a[1] a[2] a[3] a[4]
10 20 30 40 50
P 分值:2
A. 20 B. 30
C. 21 D. 31
49.以下能正确进行字符串赋值、赋初值的语句组是
分值:2
A. char s[5]={′a′,′e′,′i′,′o′,′u′};
B. char *s; s="good!";
C. char s[5]="good!";
D. char s[5]; s="good";
50.若有以下说明和定义,则对fun函数的正确调用语句是
分值:2
A. a=fun; a(w);
B. a=fun; (*a)(&c);
C. b=fun; *b(w); D. fun(b);
main( )
{
int (*a)(int*),*b( ),w[10],c;
:
:
}
fun(int *c) {...}
更多相关内容 -
Java方法递归调用实例解析
2020-08-25 02:36:41主要介绍了Java方法递归调用实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 -
python基础(十八):函数式、递归调用
2020-12-20 18:56:03文章目录一、函数式1、函数式简介2、匿名函数与lambda二、递归调用1、递归调用要点透析2、递归调用的两个过程:回溯与递推3、递归经典例题练习(1)嵌套多层的列表,要求打印出所有的元素(2)二分法递归实现 ... -
JavaScript支持的最大递归调用次数分析
2020-12-12 19:17:30你对JavaScript引擎能进行多少次递归调用好奇吗? 多少次递归调用 下面的函数可以让你找到答案: (灵感来自Ben Alman的 gist) 代码如下: function computeMaxCallStackSize() { try { return 1 + ... -
java利用递归调用实现树形菜单的样式
2020-08-26 23:25:21主要给大家介绍了关于java利用递归调用实现树形菜单样式的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧 -
vue 组件递归调用
2018-07-03 11:53:30vue组件递归调用,展示树状结构, -
Python递归调用实现数字累加的代码
2020-09-17 20:19:49今天小编就为大家分享一篇Python递归调用实现数字累加的代码,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 -
JavaScript中匿名函数的递归调用
2020-10-20 14:02:56本文主要介绍了JavaScript中匿名函数的递归调用。具有很好的参考价值,下面跟着小编一起来看下吧 -
递归调用
2019-09-26 22:50:121、递归调用: 递归调用就是在当前的函数中调用当前的函数并传给相应的参数,这是一个动作,这一动作是层层进行的,直到满足一般情况的的时候,才停止递归调用,开始从最后一个递归调用返回。 2、递归调用的方法...1、递归调用:
递归调用就是在当前的函数中调用当前的函数并传给相应的参数,这是一个动作,这一动作是层层进行的,直到满足一般情况的的时候,才停止递归调用,开始从最后一个递归调用返回。2、递归调用的方法计算4的阶乘为例代码如下:
/** * 用递归算4的阶乘 */ public class Factorial { public static void main(String[] args) { //对factorial方法进行调用 factorial(4); } //定义方法 public static int factorial(int n) { if (n == 0) { System.out.println(n + "! = 0"); return 1; } else { System.out.println(n); //用递归的方法进行阶乘处理 int temp = n*factorial(n-1); System.out.println(n + "! = " + temp); return temp; } } } 运行结果: 4 3 2 1 0! = 0 1! = 1 2! = 2 3! = 6 4! = 24
3、4的阶乘递归图解如下:
-
php+jQuery递归调用POST循环请求示例
2020-10-21 08:07:26主要介绍了php+jQuery递归调用POST循环请求,结合实例形式分析了php+jQuery的ajax方法递归调用与json转换技巧,需要的朋友可以参考下 -
函数递归调用堆栈分析.doc
2021-09-10 17:31:37函数递归调用堆栈分析.doc -
3.7 函数的递归调用(ppt).pdf
2021-12-22 13:48:573.7 函数的递归调用(ppt) -
setTimeout()递归调用不加引号出错的解决方法
2020-09-04 05:03:30用了setTimeout()想实现递归调用,如果第一个参数不加引号的话,就会出错,下面与大家分享下该如何解决 -
C语言函数递归调用PPT课件.pptx
2021-10-10 15:58:07C语言函数递归调用PPT课件.pptx -
C语言函数递归调用学习教案.pptx
2021-09-30 00:56:02C语言函数递归调用学习教案.pptx -
C语言程序设计_哈工大(3):函数的嵌套调用和递归调用.pdf
2020-03-27 13:09:13圳 职 业 技 术 学 院Shenzhen Polytechnic 六单元3函数的嵌套调用和递归调用 教学内容 函数的嵌套调用和递归调用 教学目标 应知 什么是嵌套调用什么是递归调用 应会 了解嵌套调用与递归调用时程序的执行顺序 编写... -
C#函数式编程中的递归调用之尾递归详解
2021-01-20 07:09:12普通递归和尾递归如果仅仅只是从代码的角度出发来看,我们可能发现不了他的特点,所以笔者利用两张堆栈上的图来展示具体的差距在哪,首先我们来看看普通的递归调用的情况,如下图1.1所示: 假设这里执行的函数是... -
C语言丨函数的递归调用和递归函数
2021-12-21 16:29:49如果一个对象部分地由它自己组成或按它自己定义,则我们称它是递归(Recursive)的。在日常生活中,字典就是一个递归问题的典型实例,字典中的任何一个词汇都是由“其他词汇”解释或定义的,但是“其他词汇”在被...目录
前言
如果一个对象部分地由它自己组成或按它自己定义,则我们称它是递归(Recursive)的。在日常生活中,字典就是一个递归问题的典型实例,字典中的任何一个词汇都是由“其他词汇”解释或定义的,但是“其他词汇”在被定义或解释时又会间接或直接地用到那些由它们定义的词。在数学中,数学归纳法也是递归的一种体现。
一、从阶乘引入
初学编程时,计算正整数n的阶乘是利用阶乘的定义即n!=n*(n-1)*(n-2)*...*2*1来计算的。代码如下:
#include <stdio.h> int main(void) { int i, n; long p = 1; printf("Please enter n:"); scanf("%d", &n); for (i = 1; i <= n; i++) { p = p * i; printf("%d! = %ld\n",i, p); } return 0; }
其实,还可以将n!=n*(n-1)*(n-2)*...*2*1写成n!=n*(n-1)!,即利用(n-1)!来计算n!,同理再用(n-2)!来计算(n-1)!,即(n-1)!=(n-1)*(n-2)!,以此类推,直到用1!=1逆向递推出2!,再依次递推出3!,4!,...,n!时为止。这说明阶乘是可以根据其自身来定义的问题,因此阶乘也是可递归求解的典型实例。这个递归问题可用如下的公式来表示:
下面采用递归方法来实现阶乘的计算:
#include<stdio.h> long Fact(int n); int main(void) { int n; long result; printf("Input n:"); scanf("%d", &n); result = Fact(n);//调用递归函数Fact()计算n! if (result == -1)//处理非法数据 printf("n < 0, data error!\n"); else//输出n!值 printf("%d! = %ld\n", n, result); return 0; } //函数功能:用递归法计算n!,当n >= 0时返回n!,否则返回-1 long Fact(int n) { if (n < 0)//处理非法数据 return -1; else if (n == 0 || n == 1)//基线情况,即递归终止条件 return 1; else//一般情况 return (n * Fact(n-1));//递归调用,利用(n-1)!计算n! }
可见,递归是一种可根据其自身来定义或求解问题的编程技术,它是通过将问题逐步分解为与原始问题类似的更小规模的子问题来解决问题的,即将一个复杂问题逐步简化并最终转化为一个最简单的问题,最简单的问题的解决,就意味着整个问题的解决。显然对于具体的问题首先需要关注的是:最简单的问题是什么?对于本例,n=0或1就是计算n!的最简单的问题。当函数递归调用到最简形式,即当n=1时,递归调用结束,然后逐级将函数返回值返回给上一级调用者。
二、递归模板
1.递归函数模板
一个递归函数必须包含如下两个部分:
(1)由其自身定义的与原始问题类似的更小规模的子问题,它使递归过程将持续进行,称为一般情况(General case);
(2)递归调用的最简形式,它是一个能够用来结束递归调用过程的条件,通常称为基线情况(Base case)。
代码如下:
返回值类型 Recursive(类型 形式参数1, 类型 形式参数2,……) { if (递归终止条件)//基本条件控制递归调用结束 return 递归公式的初值; else//一般条件控制递归调用向基本条件转化 return 递归函数调用返回的结果值; }
像这种“在函数内直接或间接地调用自己”的函数调用,就称为递归调用(Recursive Call),这样的函数则称为递归函数(Recursive Function)。
2.举例分析以第一目为例,基线情况是0!=1和1!=1;一般情况则是将n!表示成n乘以(n-1)!,如第一目代码中在调用函数Fact()计算n!的过程中又调用了函数Fact()来计算(n-1)!。例如要计算3!,需要经历如下步骤:
(1)在main函数中调用Fact(3)。
(2)为了计算3!,需要先调用函数Fact(3-1)计算2!。
(3)为了计算2!,需要先调用函数Fact(2-1)计算1!.
(4)计算1!时,递归终止,返回1作为1!的计算结果。
(5)返回到(3)中,利用1!=1,求出2!=2×1!=2×1=2,返回2作为2!的计算结果。
(6)返回到(2)中,利用2!=2,求出3!=3×2!=3×2=6。
(7)返回到main函数中,得出Fact(3)=6。
三、从数学归纳法理解递归
有关数学归纳法的原理,详见《人民教育出版社数学选择性必修第二册(A版)》第四章 数列 4.4*数学归纳法[2]。
下面给出数学归纳法的定义:
一般地,证明一个与正整数
有关的命题,可按下列步骤进行:
(1)(归纳奠基)证明当
时命题成立;
(2)(归纳递推)以“当
时命题成立”为条件,推出“当
时命题也成立”.
只要完成这两个步骤,就可以断定命题对从
开始的所有正整数
都成立,这种证明方法称为数学归纳法(mathematical induction).
数学归纳法的核心就在于,只要我们能证明当n=1时等式成立(基线情况),且当n=k≥1时成立能够推出n=k+1时成立(一般情况),就能说明n≥1时成立。因为只要n=1成立,n=2就成立;n=2成立,n=3就成立;……;n=k成立,n=k+1就成立。
其实递归也蕴含了数学归纳法的思想:只要给出基线情况和一般情况的递推关系,就能得到基线情况以后的所有情况。因为知道了基线情况,通过递推关系就能得出基线情况后一级的情况;知道了基线情况后一级的情况,通过递推关系就能得出再后一级的情况……因此我们在编程时只需要关心:基线情况是什么,一般情况是什么。至于复杂的函数调用关系与返回关系,可以不用理会。
四、更多递归实例
1.用递归方法编程计算Fibonacci数列
题目分析
首先我们需要找出基线情况:fib(1)=fib(2)=1;然后找出一般情况:fib(n)=fib(n-1)+fib(n-2)(n>2),即:
程序
#include<stdio.h> long Fib(int n); int main(void) { int n, i, x; printf("Input n:"); scanf("%d", &n); for (i = 1; i <= n; i++) { x = Fib(i);//调用递归函数Fib()计算Fibonacci数列的第n项 printf("Fib(%d) = %d\n", i, x); } return 0; } //函数功能:用递归法计算Fibonacci数列中的第n项的值 long Fib(int n) { if (n == 1) return 1;//基线情况 else if (n == 2) return 1;//基线情况 else return (Fib(n-1)+Fib(n-2));//一般情况 }
2.汉诺塔(Hanoi)问题
如图,A杆上从下往上按大小顺序摞着n片黄金圆盘,规定每次只能移动一个圆盘,在小圆盘上不能放大圆盘,则把圆盘从下开始按大小顺序重新摆放到第二根上需移动多少次?
移动前:
移动后:
题目分析
首先我们需要找出基线情况:假设A杆上只有2个圆盘,即汉诺塔有2层,n=2,我们的移动步骤是先将1号圆盘从A移到C,再将2号圆盘从A移到B,最后将1号圆盘从C移到B。
移动前:
第一步:
第二步:
第三步:
然后找出一般情况:我们可以将n个圆盘分为两部分,“上面n-1个圆盘”看成一个整体,于是我们的移动步骤为先将n-1个圆盘从A移到C,再将n号圆盘从A移到B,最后将n-1个圆盘从C移到B。
而把n-1个圆盘从A移到C就相当于先将n-2个圆盘从A移到B,再将n-1号圆盘从A移到C,最后将n-2个圆盘从B移到C……一直到只剩下两个圆盘,即回到基线情况。
程序
首先我们需要设计一个函数Hanoi(),Hanoi(n, 'A', 'B', 'C')表示将n个圆盘借助于C由A移动到B;接着我们要设计一个函数Move(),调用Move(n, 'A', 'B')可输出一个语句:Move n: from 'A' to 'B'.
于是得到代码如下:
#include <stdio.h> void Hanoi(int n, char a, char b, char c); void Move(int n, char a, char b); int main() { int n; printf("Input the number of disks:"); scanf("%d", &n); printf("Steps of moving %d disks from A to B by means of C:\n", n); Hanoi(n, 'A', 'B', 'C');/*调用递归函数Hanoi()将n个圆盘借助于C由A移动到B*/ return 0; } /* 函数功能:用递归方法将n个圆盘借助c从a移到b */ void Hanoi(int n, char a, char b, char c) { if (n == 2) { Move(n-1, a, c); Move(n, a, b); Move(n-1, c, b); } else { Hanoi(n-1, a, c, b); Move(n, a, b); Hanoi(n-1,c, b, a); } } /* 函数功能:将第n个圆盘从a移到b */ void Move(int n, char a, char b) { printf("Move %d: from %c to %c\n", n, a, b); }
这个程序只能实现n≥2的汉诺塔问题的求解。然而,进一步地,其实n=2也包含在n≥2的一般情况里,即可以把基线条件设成n=1,即A杆上只有一个圆盘,汉诺塔只有1层,移动操作便是将圆盘从A移到B。因此可以改写函数Hanoi()如下:
void Hanoi(int n, char a, char b, char c) { if (n == 1) { Move(n, a, b); } else { Hanoi(n-1, a, c, b); Move(n, a, b); Hanoi(n-1,c, b, a); } }
3.转置链表
定义函数,原型为struct link *Reverse(struct link *head);,功能为转置传入的链表顺序。函数不能返回一个新建的链表,必须通过改变原来的链表来实现功能,最后的返回值为转置后的链表的头节点的地址值。[3]
注意:不能通过简单地改变链表的数据域来转置链表;相反,需要改变链表的指针域。
链表节点的定义如下:
struct link { int data; struct link *next; };
题目分析
首先我们需要找出基线情况:当链表中只有2个节点时,我们只需新建一个结构体指针变量struct link* newhead;,让newhead指向第2个节点,然后让第2个节点的next指针指向第1个节点,最后让第1个节点的next指针指向NULL,最后返回newhead即可完成链表的转置。
接着我们需要找出一般情况:当链表中有n个节点(n>2)时,可把链表的后n-1个节点看成一个整体(先调用函数Reverse(head->next)使后n-1个节点的链表完成转置),这个整体与第1个节点组成一个2个节点的链表,再按照基线情况的操作,新建一个结构体指针变量struct link* newhead;,让newhead指向后n-1个节点组成的链表的头节点(这里为函数Reverse(head->next)的返回值),然后让head->next->next(第2个节点的next指针)指向头节点head,最后让头节点的next指针指向NULL,最后返回newhead即可完成链表的转置。
程序
struct link *Reverse(struct link *head) { struct link *newhead = NULL; if (head->next->next == NULL)//基线情况:只有2个节点 { newhead = head->next; head->next->next = head;//第2个节点的next指针 head->next = NULL;//第1个节点的next指针 } else//一般情况 { newhead = Reverse(head->next); head->next->next = head;//当前节点的下一个节点的next指针 head->next = NULL;//当前节点的next指针 } return newhead; }
这个程序只能完成n≥2个节点的链表的转置。然而,其实当n=2时,可以一并归入n≥2的情况中,于是我们可以把n=1甚至n=0作为基线条件(n=1即只有一个链表,n=0为空链表),修改后的程序如下:
struct link *Reverse(struct link *head) { if (head == NULL || head->next == NULL)//基线情况:空链表或链表只有1个节点 { return head; } else { struct link *newhead = Reverse(head->next); head->next->next = head;//当前节点的下一个节点的next指针 head->next = NULL;//当前节点的next指针 return newhead; } }
总结
递归将复杂的情形逐次归结为较简单的情形来计算,一直到归并为最简单的情形为止,但任何递归函数都必须至少有一个基线情况,并且一般情况必须最终能转化为基线情况,否则程序将无限递归下去,导致程序出错。
在编写和阅读递归函数的代码时,我们只需注意两点:1.基线情况是什么?2.假设上一步已经做好了,当前这一步该怎么做?(一般情况的递推关系是什么?)倘若真的想要一行行debug代码,也要假定递归的次数较少,否则将进入无穷无尽的调用与返回之中,会导致程序非常的抽象难懂。
从上述的例子可以看出,用递归编写程序更直观、更清晰、可读性更好(若不深究函数之间复杂的调用与返回关系),更逼近数学公式的表示,更能自然地描述问题的逻辑,尤其适合非数值计算领域,如Hanoi塔、骑士游历、八皇后问题。但是从程序运行效率来看,递归函数在每次递归调用时都需要进行参数传递、现场保护等操作,增加了函数调用的时空开销,导致递归程序的时空效率偏低。
参考文献:
[1]苏小红 赵玲玲 孙志岗 王宇颖 等编著 蒋宗礼 主审,C语言程序设计(第4版),高等教育出版社,P109,P158-161.
[2]主编:章建跃 李增沪,副主编:李勇 李海东 李龙才,本册主编:李龙才 周远方,编写人员:李龙才 宋莉莉 张艳娇 周远方 桂思铭 郭慧清,责任编辑:张艳娇,美术编辑:王俊宏,数学选择性必修第二册(A版),人民教育出版社,P44-52
[3]原题为:Define reverse, which takes in a linked list and reverses the order of the links. The function may not return a new list; it must mutate the original list. Return a pointer to the head of the reversed list. You may not just simply exchange the first to reverse the list. On the contrary, you should make change on rest. 题目来源于Ricky_Daxia。
-
函数的递归调用
2021-08-16 22:44:58在调用一个函数的过程中又出现直接或间接的调用该函数本身,称为函数的递归调用。 直接:在调用函数f的过程中又要调用f函数。 (简单来说在一个函数定义里面又使用了该函数,而一般用到递归调用都包含一种类似...在调用一个函数的过程中又出现直接或间接的调用该函数本身,称为函数的递归调用。
直接:在调用函数f的过程中又要调用f函数。
间接:如果在调用f1函数的过程中要调用f2函数,而调用f2函数的过程中又要调用f1函数。
(简单来说在一个函数定义里面又使用了该函数,而一般用到递归调用都包含一种类似递增递乘的有规律的变化。)
就上来看,这两种递归调用都是无终止的自身调用,显然程序中不应出现这种无终止的递归调用,这就需要用if语句来控制,只有在某一条件成立时才继续执行递归调用,否则就不再继续。
下面我们用一个典型的函数递归调用的例子来说明:
用递归的方法求n!。
解题思路:
求n!可以用递归方法,即5!==4!*5,而4!==3!*4..........
可以用下面的递归公式表示
#include <stdio.h> //求n的阶乘 int fac(int n) { if (n == 0 || n == 1) { return 1; } else {int a; a=f(n - 1) * n; return a; // 递归调用 } } int main() { int a; printf("Input a number: "); scanf("%d", &a); printf("fac(%d) = %d\n", a, fac(a)); return 0; }
分析:
调用 fac() 后即进入函数体,只有当 n==0 或 n==1 时函数才会执行结束,否则就一直调用它自身。
由于每次调用的实参为 n-1,即把 n-1 的值赋给形参 n,所以每次递归实参的值都减 1,直到最后 n-1 的值为 1 时再作递归调用,形参 n 的值也为1,递归就终止了,会逐层退出。
要想理解递归函数,重点是理解它是如何逐层进入,又是如何逐层退出的,下面我们以 5! 为例进行讲解。
递归的进入
1) 求 5!,即调用 fac(5)。当进入 factorial() 函数体后,由于形参 n 的值为 5,不等于 0 或 1,所以执行
fac(n-1) * n
,也即执行fac(4) * 5
。为了求得这个表达式的结果,必须先调用 fac(4),并暂停其他操作。换句话说,在得到 factorial(4) 的结果之前,不能进行其他操作。这就是第一次递归。
2) 调用 fac(4) 时,实参为 4,形参 n 也为 4,不等于 0 或 1,会继续执行fac(n-1) * n
,也即执行fac(3) * 4
。为了求得这个表达式的结果,又必须先调用 fac(3)。这就是第二次递归。
3) 以此类推,进行四次递归调用后,实参的值为 1,会调用 fac(1)。此时能够直接得到常量 1 的值,并把结果 return,就不需要再次调用 fac() 函数了,递归就结束了。注意:递归结束时fac(1)满足if语句上半句,a被赋值为1,并且通过return语句将a=1返还给fac函数
即fac(1)=返还值(函数值)
递归的退出
当递归进入到最内层的时候,递归就结束了,就开始逐层退出了,也就是逐层执行 return 语句。
1) n 的值为 1 时达到最内层,此时 return 出去的结果为 1,也即 factorial(1) 的调用结果为 1。
2) 有了 fac(1) 的结果,就可以返回上一层计算fac(1) * 2
的值了。此时得到的值为 2,return 出去的结果也为 2,也即 fac(2) 的调用结果为 2。
3) 以此类推,当得到 fac(4) 的调用结果后,就可以返回最顶层。经计算,fac(4) 的结果为 24,那么表达式fac(4) * 5
的结果为 120,此时 return 得到的结果也为 120,也即 fac(5) 的调用结果为 120,这样就得到了 5! 的值。希望对于初学的你一些启示!
-
函数递归调用
2021-05-26 16:33:42微信公众号搜索【程序媛小庄】,...函数递归就是函数的递归调用,是函数嵌套调用的一种特殊形式,具体就是指在调用一个函数的过程中直接或者间接的调用到本身,递归的本质就是循环做重复的事情。 在调用func的过程中. -
Python函数递归调用实现原理实例解析
2020-12-17 09:06:43函数的递归调用: 是函数嵌套调用的一种特殊形式 具体是指: 在调用一个函数的过程中又直接或间接地调用到了本身 # 直接调用本身 def func(): print('我是func') func() func() # 函数会不断的运行永远不会结束... -
C语言递归函数(递归调用)详解[带实例演示]
2021-12-23 22:04:26一个函数在它的函数体内调用它自身称为递归调用,这种函数称为递归函数。执行递归函数将反复调用其自身,每调用一次就进入新的一层,当最内层的函数执行完毕后,再一层一层地由里到外退出。 递归函数不是C语言的... -
【函数递归调用】递归调用经典问题—汉诺塔问题
2020-07-20 10:58:571.函数的递归调用 函数可以直接或者间接的调用其自身,这称为函数的递归调用。递归算法的实质是将原有的问题逐层拆解为新的问题,而解决新的问题又用到了原问题的解法,因此可以继续调用自身分解,按照此原则一直... -
vue 组件如何递归调用自己
2022-02-10 16:42:19第一点:要用好name属性,递归调用 第二点:要用好v-if,限制递归的条件,不能无限制递归下去,只能满足某一条件才能渲染。 -
C语言函数的递归和调用实例分析
2020-09-05 03:21:09一个函数在它的函数体内调用它自身称为递归调用。这种函数称为递归函数。C语言允许函数的递归调用。在递归调用中,主调函数又是被调函数。执行递归函数将反复调用其自身,每调用一次就进入新的一层 -
C语言中的递归调用
2021-05-19 18:30:56递归:这个词简直是大多数初学者的噩梦,当初学者在接触递归时,简直...一、递归的介绍:C语言中的函数都支持递归,递归换句话说就是自己调用自己,递归分为直接调用自己跟间接调用自己,其实只要直接调用自己能理解... -
c语言允许函数的递归调用吗
2021-05-22 04:21:16c语言允许函数的递归调用吗允许。C语言中的函数直接或间接调用自己的过程叫递归。一、递归的两个必要条件1、存在限制条件,当满足这个条件时,递归便不再继续。2、每次递归调用之后越来越接近这个限制条件。二、经典... -
JAVA实现遍历文件夹下的所有文件(递归调用和非递归调用)
2020-08-31 14:17:47本篇文章主要介绍了JAVA 遍历文件夹下的所有文件(递归调用和非递归调用) ,具有一定的参考价值,有兴趣的可以了解一下。