实验8 函数——递归函数
淮海工学院计算机科学系实验报告书
课程名：《C语言程序设计A 》
题目：实验8 函数
——递归函数
班级：软嵌151
学号：2015123349
姓名：陈正宁
1、实验内容或题目
（1）用递归编写n!的函数，并在main主函数中调用此函数。
（2）有n个大小不同的盘片从大到小放在A柱上，另有B和C两个空柱，要求将这n个盘片从A柱搬到C柱上，在搬动过程中，每次只能搬一个盘片，而且小的不能放在大的之下。编写hanio函数实现搬迁过程。
（3）编写一个程序，求解皇后问题：在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。
2、实验目的与要求
（1）要求熟练掌握函数的定义和调用，熟悉函数返回值的使用。
（2）熟悉函数调用的方式和过程。
（3）重点掌握递归函数的使用。
（4）要求实验的第2题采用递归函数编写，盘片的数目在main主函数中输入。提示：函数的参数定义如hanio(n,A,C,B),表示将n个盘片从A柱通过C柱搬到B柱。
（5）要求实验的第3题采用递归函数编写皇后的个数n由用户输入，其值不能超过20；采用整数数组q[N]求解结果，因为每列只能放一个皇后，q[i]的值表示第i个皇后所在的行号，即该皇后放在(q[i]，i)的位置上。求解皇后问题的递归模型如下：place(i，n)：若i=n，则n个皇后放置完毕，输出解（输出q数组元素）
place(k，n)：在第k列找一个合适位置i，放置一个皇后（即q[k]=i）；place(k+1，n)；其中，place(k，n)表示前面的第1，…，k-1个皇后放置好后，现在用于放置k，…，n的皇后。
3、实验步骤与源程序
⑴实验步骤
⑵源代码
（1）、
#include
long fac(int n)
{
long f;
if(n==0||n==1)
f=1;
else
f=n*fac(n-1);
return (f);
}
void main()
{
int n;
printf("请输入一个整数n:");
scanf("%d",&n);
printf("%d!=%d\n",n,fac(n));
}
（2）、
#include
int main()
{
void hanio(int n,char A,char C,char B);
int m;
printf("请输入盘片的数量:");
scanf("%d",&m);
printf("移动%d个盘片的步骤如下:\n",m);
hanio(m,'A','B','C');
return 0;
}
void hanio(int n,char one, char two, char three) {
void move(char x,char y);
if(n==1)
move(one,three);
else
{
hanio(n-1,one,three,two);
move(one,three);
hanio(n-1,two,one,three);
}
}
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}
（3）、
#include
#include
const int N=20;
int q[N];
int cont=1;
void print(int n)
{
int i;
printf("第%2d个解：",cont);
for (i=1;i<=n;i++)
printf("%d ",q[i]);
cont++;
printf("\n");
}
int find(int i,int k)
{
int j;
j=1;
while (j { if ((q[j]==i) || (abs(q[j]-i)==abs(j-k))) return 0; j++; } return 1; } void place(int k,int n) { if (k>n) print(n); else for (int i=1;i<=n;i++) if (find(i,k)) { q[k]=i;place(k+1,n); } } int main() { int n; int result; printf("皇后问题(n<20)\n"); printf("输入摆放的皇后个数：\n n="); scanf("%d",&n); if (n>20) { printf("n值太大,不能求解\n"); result=1; } else if(n>0&&n<4) { printf("不存在皇后问题!"); printf("\n"); result=0; } else { printf("有%d个皇后问题求解如下：\n",n); place(1,n); printf("\n"); result=1; } return result; } 4、测试数据与实验结果（可以抓图粘贴）（1）、 （2）、 （3）、 5、结果分析与实验体会 （1）、在调用一个函数的过程中又出现或间接地调用函数本身，称为函数的递归调用。 （2）、必须与函数的嵌套调用区分开。 （3）、如果要求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件！ 递归调用详解，分析递归调用的详细过程 2009年05月23日星期六 22:52 一、栈 在说函数递归的时候，顺便说一下栈的概念。 栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。 再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。 可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。 二、递归 递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级 实验八公式、序列及函数的使用 一、实验目的 1．熟练掌握序列填充及公式复制的方法； 2．掌握常用函数的功能及使用方法，并能用它们来解决一些实际问题。 二、实验内容与操作步骤 在Excel环境下完成以下各操作： （一）序列填充及公式的使用 1．在Excel中创建一个空白工作簿 2．利用Excel提供的数据填充功能，在Sheet1工作表中输入以下数据： ⑴在区域A1：A9中从上到下填入：2，4，6，8，10，12，14，16，18 ⑵在区域B1：B9中从上到下填入：1，2，4，8，16，32，64，128，256 ⑶在区域C1：C12中从上到下填入：JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC ⑷在区域D1：D7中从上到下填入：星期日，星期一，星期二，星期三，星期四，星期五，星期六 3．在Sheet2工作表中，利用公式计算二次函数ax2+bx+c的值，其中a=2，b=3，c=5，x从-3到4变化，每隔0.5取一个函数值。操作方法写出如下： 4．把工作簿以E81.XLS为文件名存入D:\EX8中。 （二）函数的使用 在Excel环境下打开D:\EX8\E82.XLS文件,依次完成以下各操作后按E83.XLS为文件名存入D:\EX8中。 1、统计函数的使用 ⑴单击“统计函数”工作表； ⑵在区域F3:G8中用“统计函数”计算出各分店的统计值。 操作方法是：先在F3单元及G3单元输入的计算公式,然后选定区域F3：G3后双击其填充柄。其中F3单元的公式为，G3单元的公式为。 ⑶在区域B9:E12用“统计函数”计算出各季度的统计值。 2、条件函数的使用 ⑴单击“条件函数”工作表。 ⑵计算出各学生的平均分； ⑶给定各学生的成绩等级，规则如下：平均分≥90为“A”，80≤平均分＜90为“B，70≤平均分＜80为“C”，60≤平均分＜70为“D”，平均分＜60为“E”。以此规则在区域F3:F62用IF函数确定各学生的等级。 ⑷用FREQUENCY函数在区域I2：I5中统计出平均分0~59，60~79，80~99，100各分数段的学生人数。 3、文本函数的使用 ⑴单击“文本函数”工作表； ⑵在区域A2:F32给出的数据清单中，编号的前3位为系别信息，101为数学系，102为物理系，103为化学系，据此在区域B3:B32用函数求出每位教师的系别。其中B3单元使用的公式为。 ⑶已知身份证号的第7至第10位数为出生年份，据此在区域F3:F32用函数求出每位教师的出生年份。其中F3单元使用的公式为。 4、日期函数的使用 ⑴单击“日期函数”工作表； ⑵在区域A2:F32给出的数据清单中，在区域E3:E32用日期函数求出每位职工的工龄。其中E3单元使用的公式为。 ⑶在区域F3:F32用日期函数求出每位职工的工作天数（即自参加工作以来已经过的总天数。其中F3单元使用的公式为。 5、财务函数的使用 使用 PMT 函数完成以下有关的操作： ⑴单击“财务函数”工作表； ⑵某企业向银行贷款5 万元，准备4年还清，假定当前年利率为 4 % ，在 B5 单元 计算每个月应向银行偿还贷款的数额，根据条件在 B2 : B4 补充所需内容。其中单元格B5 使用的公式为。 ⑶假定当前年利率为 5 %，为使 5 年后得到 10 万元的存款，在 D5 单元计算现在开 递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值，那么可以很容易地写成这样： 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计 算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算 )1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上 一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。 用图解来说明，就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为 递归算法详解标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N] 递归 冯文科一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简 a与前面临近几项之间的关单，于是人们想出另一种办法来描述这种数列：通过初值及 n 系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： a的值，那么可以很容易地写成这样： 如果需要写一个函数来求 n 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数) f为例。如在求)3(f时，由于3不是特殊值，因此需 (n 要计算)2( 3f，但)2(f是对它自己的调用，于是再计算)2(f，2也不是特殊值，需要计 * 算)1( f，返回 )1(= 2f，需要知道)1(f的值，再计算)1(f，1是特殊值，于是直接得出1 * 上一步，得2 3 * )2( )3(= = f，从而得最终 =f )1( 3 2 * * )2(= =f 2 f，再返回上一步，得6 解。 用图解来说明，就是 实验8 函数(一)实验目的: 1、理解自定义函数过程的定义与调用方法; 2、掌握自定义函数的定义与调用方法; 3、理解函数中的参数的作用; 实验内容: 1、编写一函数Fabonacci(n),其中参数n代表第n 次的迭代。While循环 def fib(n): if n==1 or n==2: return 1 a=1 b=1 i=2 while True: c=a+b a=b b=c i+=1 #第i次迭代,也就就是第i个数 if i==n: return c break def main(): n=input("Enter a number of generation:") print fib(n) main() 或者用for循环 def fib(n): a=1 b=1 c=0 if n==1 or n==2: return 1 else: for i in range(3,n+1): c=a+b a=b b=c return c def main(): n=input("enter n:") print fib(n) main() 2、编写一函数Prime(n),对于已知正整数n,判断该数就是否为素数,如果就是素数,返回True,否则返回 False。 def prime(n): if n<2: return False a=0 for i in range(1,n+1): if n%i==0: a+=1 if a>2: return False else: return True def main(): n=input("Enter a number:") print prime(n) main() Or: def prime(n): if n<2: return False if n==2: return True for i in range(2,n): if n%i==0: return False return True def main(): n=input("Enter a number:") print prime(n) main() 实验1 cin、cout及面向过程的编程实验2 引用与函数重载 实验3 类与对象 实验4 静态成员与对象参数 实验5 拷贝构造函数与内存分配 实验6 对象数组与子对象 实验7 含有数组成员的对象与深拷贝实验8 运算符重载(1) 实验9 运算符重载(2) 实验10 继承与派生 实验11 虚函数与类族 实验12 STL 实验1 cin 、cout 及面向过程的编程 1A ：显示某个日期是星期几 (1) 输入、输出要求： 输入：3个正整数，依次为年、月、日，比如2049 10 1 输出：按类似“[2049-10-5] is Friday.”的形式输出 示例： (2) 处理方法 历史上的某一天是星期几？未来的某一天是星期几？关于这个问题，有很多计算公式，其中最著名的是蔡勒(Zeller)公式。即 7)%110)1(26244(-+? ?? ???++-??????+??????+=d m c c y y w 公式中的符号含义： w ——星期几 c ——年份的前两位 y ——年份的后两位 m ——月，3≤m ≤14，某年的1、2月视为上一年的13、14月，比如2003年1月1日要看作2002年的13月1日 d ——日 ??——代表取整，即只要整数部分 %——除法求余数 例如：对于2049年10月1日，计算过程如下： 5 7%547)%284051249(7)%1110)110(2620242044949(==+-++=-+??? ???++?-??????+??????+=w 即2049年10月1日是星期5。如果计算结果是负数，则加7。 1B ：格式化输出实数 从键盘读取本金和年利率，求20年中每年末本息合计有多少钱。 输入：用空格分隔的两个数，都可以带小数点 输出：以“钱数（？年后）”的方式显示，以“2格、右对齐”的方式显示年，以“共10格、小数点后取2位、右对齐”的方式显示本息合计的钱数，见示例 示例：本金973.45元、年利率2%的显示结果如下 递归算法详细分析－> C阅读(17418) C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267 除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。 实验八函数 【目的与要求】 1．掌握C语言函数的定义方法、函数的声明及函数的调用方法。 2．了解主调函数和被调函数之间的参数传递方式。 【上机内容】 【一般示例】 【例1】将打印18个"*"组成星形线定义为一个返回值和形参列表都为空的函数，通过主函数调用它。 #include #include 深入理解递归函数 刚开始接触编程对递归调用都是比较头痛，很多年前我也会一样。昨天晩上睡觉突然想起了谭浩强C语言的汉诺塔递归调用，记得当吋是在高中的时候，我表姐在上大学，她把谭浩强的C语言给了我，只看书不实践，现在想起来效果还真差。其中递归调用汉诺塔看了好久都没有整明白，直到上大学学习C语言也还没有搞明白，当学到递归调用了，我就去问老师，老是说回去看看，下周告诉我。谁知到老师真的很忙，下周也没有结果。后来自己什么吋候明白的也忘记了。 刚开始接触递归都会告诉你，递归占用资源，使程序复杂，最好不要使用；还有人说，如果这个人一来就是用递归，我肯定不会聘用他。但是我认为这些观点太片面。递归算法的目的降低程序的复杂度，解放大脑负担，让大脑更加专注于问题本身。程序的性能跟递归没有什么关系，更重要的时算法本身，我们会在稍后讲解一下同i种算法同样是递归，性能的差异巨大。设计模式中，很多模式都存在递归。 刚开始接触递归的，往往都会在里面打圈圈，自己越绕越晕，觉得递归太复杂。其实看待递归的时候，也是要分层面看待，不要把自己的大脑当做是电脑，可以绕很多的圈圈，有人说人的大脑同时能处理7个左右的变量，绕一圈就多几个变量，能绕几圈啊。呵呵。找到一个算法，在编写算法的吋候，只考虑一次递归所做的事情，如果遇到到递归调用函数的时候，把他当做一个函数整体考虑，他能完成他要完成的事情，要相信他，也要相信自己。我们所在的层面就是算法的层面，或者一次执行的层面。如果在算法层面和递归调用层面来回穿插的思考，读懂递归算法将非常困难，递归的复杂度就在于压栈会导致大量的变量需要存储，对我们的大脑来说负担太重，但是对汁算机来说是小意思，相对来说算法层面往往很简单，所以我们一定要站在算法层面考虑问题，而不是递归层面。 下面来看我如何一步一步实现汉诺塔：(VS2010C#控制台程序) [csharp] view plaincopyprint^C 1.class Program 2?{ 3?static void Main(string[] args) 4.< 实验八 函 数(二) 参考答案 /*1.(sy8-1.c ) 请编写函数 fun ，其功能是：计算并输出给定数组（长度为 9）中每相邻两个元素之平均值的平方根之和。 例如，给定数组中的 9 个元素依次为 12.0、34.0、4.0、23.0、34.0、45.0、18.0、3.0、11.0，输出应为：s=35.951014。 【解题思路】 在给出的参考程序中，由于函数要求的返回值为双精度型，所以先将变量 avg 、sum 定义为双精度型，初值为 0.0，然后通过 for 循环分别求出相邻两个元素的平均值放入变量 avg 中，再使用求平方根函数sqrt()对各平均值开方求和，最终结果输出到变量 sum 中并返回。 【参考答案】*/ double fun(double x[9]) { int i ; double avg=0.0,sum=0.0; //将变量avg 、sum 定义为双精度型，并给其赋初值为0.0 for (i=0;i< 8;i++) { avg=(x[i]+x[i+1])/2; //通过for 循环分别求出相邻两个元素的平均值放入变量avg 中 sum+=sqrt(avg); //使用求平方根函数sqrt()对各平均值开方求和，最终结果输出到变量 sum } return sum; /*返回计算结果*/ } 2.(sy8-2.c ) 编写函数fun ，实现矩阵（3行3列）的转置(即行列互换)。例如，输入下 面的矩阵：????? ??900800700600500400300200100，程序输出: ???? ? ??900600300800500200700400100。 【解题思路】 方阵转置，只需要将左下半三角元素和右上半三角元素对换即可。 【参考答案】 int fun(int array[3][3]) { int i,j,t ; for(i = 0 ; i < 3 ; i++) for(j = 0 ; j < i ; j++) {t=array[i][j]； array[i][j]=arrar[j][i]； array[j][i]=t ; } } 3.(sy8-3.c ) 请编写函数 fun ，函数的功能是：统计一行字符串中单词的个数作为函数值返回。一行字符串在主函数中输入，规定所有单词由小写字母组成，单词之间由若干个空格隔开，一行的开始没有空格。 【解题思路】I am a student! 在给出的参考程序中，若判断出当前字符为非空格，而它前面的字符是空格，则单词数累加 1；若当前字符为非空格，而其前面的字符也为非空格，则单词数不累加 1，程序细节可以参考程序的注释部分。 【参考答案1】 int fun( char s[]) 递归，作为C语言最经典的算法之一，是一种非常有用的程序设计方法。虽然用递归算法编写的程序结构清晰，具有很好的可读性，还往往使某些看起来不易解决的问题变得容易解决。但在递归函数中，由于存在着自调用过程，程序控制反复进入其自身，使程序的分析设计有一定困难，致使很多初学者往往对递归迷惑不解，也在这上面花了不少的时间，却收效甚微。那么，究竟什么是递归?怎么实现递归呢? 所谓递归，简而言之就是在调用一个函数的过程中又直接或间接地调用该函数本身，以实现层次数据结构的查询和访问。在函数中直接调用函数本身，称为直接递归调用。在函数中调用其它函数，其它函数又调用原函数，这就构成了函数自身的间接调用，称为间接递归调用。 而采用递归方法来解决问题，必须符合以下三个条件： 1、可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。 说明：解决问题的方法相同，调用函数的参数每次不同（有规律的递增或递减），如果没有规律也就不能适用递归调用。 2、可以应用这个转化过程使问题得到解决。 说明：使用其他的办法比较麻烦或很难解决，而使用递归的方法可以很好地解决问题 3、必定要有一个明确的结束递归的条件。 说明：一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。 好知道是这样以后;我们来写一个众多教材上的程序：使用递归的方法求n!。 当n>1时，求n!的问题可以转化为n*(n-1)!的新问题。比如n=4： 第一部分：4*3*2*1 n*(n-1)! 第二部分：3*2*1 (n-1)(n-2)! 第三部分：2*1 (n-2)(n-3)! 第四部分：1 (n-4)! 4-4=0，得到值1，结束递归。 我给的源程序如下： #include 实验十函数应用 一?实验目的 1.掌握函数的定义和调用； 2.理解形参和实参的使用和传值调用； 3.理解函数声明的使用； 4.掌握函数的嵌套调用； 5.了解函数的嵌套与递归调用，掌握递归函数的编写规律； 6.了解数组元素、数组名作函数参数。 二?实验学时数 2学时 三?实验步骤 (一)阅读程序 1．#include x=x-y; printf("%d,%d\n",x,y); 3．#include 1．什么是递归函数(recursive function) 递归函数即自调用函数，在函数体内部直接或间接地自己调用自己，即函数的嵌套调用是函数本身。 例如，下面的程序为求n!： long fact(int n) { if(n==1) return1； return fact(n-1)*n；／／出现函数自调用 } 2．函数调用机制的说明 任何函数之间不能嵌套定义，调用函数与被调用函数之间相互独立(彼此可以调用)。发生函数调用时，被调函数中保护了调用函数的运行环境和返回地址，使得调用函数的状态可以在被调函数运行返回后完全恢复，而且该状态与被调函数无关。 被调函数运行的代码虽是同一个函数的代码体，但由于调用点，调用时状态，返回点的不同，可以看作是函数的一个副本，与调用函数的代码无关，所以函数的代码是独立的。被调函数运行的栈空间独立于调用函数的栈空间，所以与调用函数之间的数据也是无关的。函数之间靠参数传递和返回值来联系，函数看作为黑盒。 这种机制决定了C／C++允许函数递归调用。 3．递归调用的形式 递归调用有直接递归调用和间接递归调用两种形式。 直接递归即在函数中出现调用函数本身。 例如，下面的代码求斐波那契数列第n项。斐波那契数列的第一和第二项是1，后面每一项是前二项之和，即1，1，2，3，5，8，13,...。代码中采用直接递归调用： long fib(int x) { if(x>2) return(fib(x-1)+fib(x-2))；//直接递归 else return1； } 间接递归调用是指函数中调用了其他函数，而该其他函数却又调用了本函数。例如，下面的代码定义两个函数，它们构成了间接递归调用： int fnl(int a) { int b； b=fn2(a+1)；//间接递归 //... 淮海工学院计算机科学系实验报告书 课程名：《C语言程序设计A 》 题目：实验8 函数 ——递归函数 班级：软嵌151 学号：2015123349 姓名：陈正宁 1、实验内容或题目 （1）用递归编写n!的函数，并在main主函数中调用此函数。 （2）有n个大小不同的盘片从大到小放在A柱上，另有B和C两个空柱，要求将这n个盘片从A柱搬到C柱上，在搬动过程中，每次只能搬一个盘片，而且小的不能放在大的之下。编写hanio函数实现搬迁过程。 （3）编写一个程序，求解皇后问题：在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。 2、实验目的与要求 （1）要求熟练掌握函数的定义和调用，熟悉函数返回值的使用。 （2）熟悉函数调用的方式和过程。 （3）重点掌握递归函数的使用。 （4）要求实验的第2题采用递归函数编写，盘片的数目在main主函数中输入。提示：函数的参数定义如hanio(n,A,C,B),表示将n个盘片从A柱通过C柱搬到B柱。 （5）要求实验的第3题采用递归函数编写皇后的个数n由用户输入，其值不能超过20；采用整数数组q[N]求解结果，因为每列只能放一个皇后，q[i]的值表示第i个皇后所在的行号，即该皇后放在(q[i]，i)的位置上。求解皇后问题的递归模型如下：place(i，n)：若i=n，则n个皇后放置完毕，输出解（输出q数组元素） place(k，n)：在第k列找一个合适位置i，放置一个皇后（即q[k]=i）；place(k+1，n)；其中，place(k，n)表示前面的第1，…，k-1个皇后放置好后，现在用于放置k，…，n的皇后。 3、实验步骤与源程序 ⑴实验步骤 ⑵源代码 （1）、 #include 实验5 函数 姓名：学号：实验日期： 1.实验目的和要求：参见实验指导书实验八 2.实验内容和步骤： 实验内容：实验指导书中的实验八 实验步骤： 2.1.实验内容的第1题，通过本题，了解到要在单步调试时能够观察自定义的函数内部变量变化情况，单步调试如何操作： 1.在“菜单栏”中单击“组建”，然后在弹出的下划栏中选择“开始调试”，然后选择“Step Into”；或者按“F11”。 2.然后开始单步调试，按F10 提问 修改前运行结果画面： （1），请在下面粘贴运行结果画面： #include 实参a是否为同一变量？不是 提问（2），请请在下面粘贴运行结果画面：#include int a=3,b=5; 通过本题，可以得出什么结论？若没给未知量赋予初值，那未知量将被随意赋值，赋值一主函数的赋值为先。 2.2 实验内容部分第2题源程序代码，请贴图： 程序运行结果画面，请贴图： 2.3 实验内容部分第3题源程序代码，请贴图： 递归算法详解 C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。 在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。 /*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/ 实验8 参考答案 二、实验内容与操作步骤 (二) 函数的使用 1、统计函数的使用 其中F3单元的公式为=SUM(B3：E3) ，G3单元的公式为=A VERAGE（B3：E3）。 2、条件函数的使用 ⑶其中F3单元使用的公式为： =IF（E3>=90，”A”，IF（E3>=80，”B”，IF（E3>=70，”C”，IF（E3>=60，”D”，”E”））））。 然后双击F3单元的填充柄。 ⑷具体的操作步骤及计算公式如下： （1）在区域H2:H4输入统计间距数据59.9,79.9,99.9； （2）选定作为统计结果数据的输出区域:I2:I5； （3）输入频度分析统计函数的公式：=FREQUENCY（E3：E62，H2：H4）； （4）按[Ctrl]+[Shift]+[Enter] 3、文本函数的使用 ⑵其中B3单元使用的公式为 =IF（LEFT(A3,3)=”101”，”数学系”，IF（LEFT(A3,3)=”102”，”物理系”，”化学系”））。 ⑶其中F3单元使用的公式为 =MID(E3,7,4) 。 4、日期函数的使用 ⑵其中E3单元使用的公式为 =YEAR（TODAY（））-YEAR（D3）+1 。 ⑶其中F3单元使用的公式为 =TODAY（）-D3 。 5、财务函数的使用 ⑵其中B5单元使用的公式为 =PMT（B2/12，B3*12，B4）。 ⑶其中E5单元使用的公式为 =PMT（E2/12，E3*12，，E4）。 6、排位函数的使用 ⑵其中G2单元使用的公式为 =F2-$B$10 。 ⑶其中H2单元使用的公式为 =RANK(F2,$F$2:$F$8,1) 或 =RANK(G2,$G$2:$G$8,1) 。 三、思考与练习 1、具体的操作步骤及计算公式如下： (1) 在区域F10:F13输入统计间距数据99,199,299,399； (2) 选定作为统计结果数据的输出区域:G10:G14； (3) 输入频度分析统计函数的公式：=FREQUENCY（C3：C23，F10：F13）； (4) 按[Ctrl]+[Shift]+[Enter] 2、操作步骤及计算公式： 递归程序设计 1．计算最大约数gcd(m,n)可用递归形式定义如下：若m%n等于0，则gcd(m,n)等于n 否则，gcd(m,n)等于gcd(n,m%n)。 #include else return gcd(n , m %n ); } int main(){ int m, n; cout << "n="; cin >> n; cout << "m="; cin >> m; cout << gcd(m, n); system("pause"); return 0; }。 2．编写一递归函数，计算下面的级数： i i m 1......31211)(++++= #include 实验八 函 数(二) 参考答案 1.(sy8-1.c ) 请编写函数 fun ，其功能是：计算并输出给定数组（长度为 9）中每相邻两个元素之平均值的平方根之和。 例如，给定数组中的 9 个元素依次为 1 2.0、34.0、4.0、2 3.0、3 4.0、4 5.0、18.0、3.0、11.0，输出应为：s=35.951014。 【解题思路】 在给出的参考程序中，由于函数要求的返回值为双精度型，所以先将变量 avg 、sum 定义为双精度型，初值为 0.0，然后通过 for 循环分别求出相邻两个元素的平均值放入变量 avg 中，再使用求平方根函数sqrt()对各平均值开方求和，最终结果输出到变量 sum 中并返回。 【参考答案】 double fun(double x[9]) { int i ; double avg=0.0,sum=0.0; //将变量avg 、sum 定义为双精度型，并给其赋初值为0.0 for (i=0;i< 8;i++) { avg=(x[i]+x[i+1])/2; //通过for 循环分别求出相邻两个元素的平均值放入变量avg 中 sum+=sqrt(avg); //使用求平方根函数sqrt()对各平均值开方求和，最终结果输出到变量 sum } return sum; /*返回计算结果*/ } 2.(sy8-2.c ) 编写函数fun ，实现矩阵（3行3列）的转置(即行列互换)。例如，输入下 面的矩阵：????? ??900800700600500400300200100，程序输出: ???? ? ??900600300800500200700400100。 【解题思路】 方阵转置，只需要将左下半三角元素和右上半三角元素对换即可。 【参考答案】 int fun(int array[3][3]) { int i,j,t ; for(i = 0 ; i < 3 ; i++) for(j = 0 ; j < i ; j++) t=array[i][j], array[i][j]=arrar[j][i], array[j][i]=t ; } 3.(sy8-3.c ) 请编写函数 fun ，函数的功能是：统计一行字符串中单词的个数作为函数值返回。一行字符串在主函数中输入，规定所有单词由小写字母组成，单词之间由若干个空格隔开，一行的开始没有空格。 【解题思路】 在给出的参考程序中，若判断出当前字符为非空格，而它前面的字符是空格，则单词数累加 1；若当前字符为非空格，而其前面的字符也为非空格，则单词数不累加 1，程序细节可以参考程序的注释部分。 【参考答案】 int fun( char s[]) { int i,word=0,num=0;/*word 标志是否是单词，num 用来记录单词数*/ for(i=0;s[i]!=?\0?;i++)递归调用详解,分析递归调用的详细过程
实验八 公式、序列及函数的使用
递归算法详解
递归算法详解完整版
Python 实验8 函数1
面向对象实验题及答案(全)
(重要)递归(含代码执行过程解释)
实验八 函数含答案
深入理解递归函数.docx
大学生c语言程序设计(第四版谭洪强)实验8答案
C语言函数递归[1]
实验十函数应用答案
什么是递归函数
实验8 函数——递归函数
《C语言程序设计》实验.设计.习题.答案 函数
递归算法详解
实验八参考答案
递归练习题(新、选)
实验八 参考答案