下载文档原格式
二级C++函数：递归函数引言在调用一个函数的过程中有出现直接或间接地调用该函数本身,称为函数的递归调用.对于初学者来说,递归函数是比较难以理解的.现在的程序设计的教材对于递归都比较简单,例子从一开始较难理解.加之不了解函数调用在计算机中的实现过程就更难理解递归调用了.这篇文章从初学者的角度对递归给予了一定的解释.从一个简单的数学题开始有一个等差数列,首项是3,公差是2,求第5项a5.我想这是所有高中生都会的题.再简单不过,只要知道通项公式an=a1+(n-1)k (这里k是公差) 代入即可. 大家都知道通项是由递推公式推导来的,递推公式直接用数学语言反映了等差数列的性质,an=a(n-1)+k.如果大家不知道通项公式,那么在这道题中,计算的方法是:a2=a1+2;a3=a2+2;a4=a3+2;a5=a4+2.知道a5=11,经过5次计算便可以得到a5的值.如果计算机也不知道通项公式,在如果我们要计算第一百项,亦或是第一万项,我们难道要a2=a1+2;a3=a2+2......a10000=a9999+2 这样来计算吗.当然不是,我们可以用递归函数实现,而a2=a1+2;a3=a2+2......a10000=a9999+2 的过程便是递归的回推过程,可是计算机确实没有我们广大高中生聪明,它不知道直接这样求解,呵呵.在计算机中的实现要说清楚递归函数的实现就要了解程序里函数嵌套调用在计算机中的实现过程.我们来看下面一个函数的调用,这里我们用类似C语言的函数形式:f(){ .... //其他代码g(a); //调用函数g(),参数是areturn ... //函数的返回值}//----------------------------------------------------------- main() //主函数{ ..... //其他代码f(b); //调用函数f(),参数是b}主函数在执行的过程中调用了函数f(),而f()其自身又调用了另一个函数g().那么这种嵌套调用在计算机中又是怎么实现的呢?在函数的执行过程中,系统用到了栈内存.栈是一种数据结构,就是有特定数据存取方式的容器.栈使用的存取方式称为后进先出LIFO(late in first out),也就是后面放入的数据先离开栈,最先放入的数据最后离开.大家可以把栈看成一个和盘子一样大小放的水槽,放入其中的盘子只能从最上面依次取走,不下面的盘子只能等它上面的取走之后才能取出.栈是一种在计算机中非常重要的数据结构,它后进先出的性质也直接关系到了函数嵌套调用在计算机中的实现.当一个函数的执行过程中需要调用另一个函数时,需要保留现场,意思是系统保存现有的所有数据,把他们放入栈内存,称为压入栈.之后就转到要调用的那个函数处执行了,并把参数传给它.等到调用的那个函数执行完了,系统就把刚才压入栈内存的数据都取出,称为弹出栈.并且把他调用的函数的返回值给原函数.如果被调用的函数中还要调用其他函数,系统也按照上述的方法保存和取回数据.栈的性质能很好得适用于这一过程.在来看递归函数,按引言里的意思,在上述的过程中被调用的函数就是调用函数自己.其实现的过程是一样的.是不是很简单?再看一些例子文章开始等差数列的例子写成函数就是(方便起见,值都设为整数):int getan(int n, int a1) // 要求第n项,a1为已知的首项{if(n==1)return a1; //如果n=1,返回a1的值,这是递归得以结束的关键elsereturn getan(n-1,a1)+2 ; //不等于1,则再次调用自身求出第n-1项,返回结果加上公差2}//------------------------------------------------------- main() //主函数{int a1=3; //设首项int a5=getan(5,3); //递归求解第5项a5printf(d%,a5); //输出}递归函数调用自身是一个不断循环过程,就像循环语句需要有条件让它停止循环,否则就陷入了无限循环之中,那后果......天啊!所以if(n=1) return a1;就是停止递归的条件.我们来仔细地看一下a5是如何求出的,不要嫌罗嗦,来:首先当主函数执行到int a5=getan(5,3); 开始求 a5的值.n=5>1 所以gatan()函数又调用自身,并把参数5-1=4和3传给下一个函数,所以执行getan(4,3);n=4>1 gatan()函数再次调用自身,并把参数3和3传给下一个函数,所以执行getan(3,3);n=3>1 执行getan(2,3);n=2>1 执行getan(1,3);终于,n=1了,现在getan(1,3)的返回值是3.getan(2,3); 返回值是3+2=5.getan(3,3);返回7.getan(4,3);返回9.最后getan(5,3);返回11,变量a5=11,结果也就出来了.从理论上我们把函数反复调用自身的过程称为递推的过程,而每个函数的返回称之为回推.递推的过程把复杂的问题一步步分解开,直到出现最简单的情况,就像已知a1=3.得到了最简单情况的解,就可以回推回去得出原来复杂问题的答案了.要说明的一点是,在这里我们认为函数的使用者总是正确的,不会把诸如-1,0,5.2等之类不合理项数作为参数输入,所以没有做出错检查.另外,刚才的函数中我们在其内部设了公差2,其实可以有更一般的情况,将公差k由参数传入:getan(int n, int a1, int k){if(n==1) return a1;else getan(n-1,a1,k);}结束这个例子前还是不得不说一句,我们是在假设不知道通项公式的情况下,为了说明问题才抛出这个例子,其实可以这样:getan(int n, int a1, int k){return a1+(n-1)*k; //使用通项公式求解}喔,计算机这下聪明了.在来看一个典型的求阶乘的例子n! 数学上,阶乘公式是: n!=1 (当n=1,0)n!=n(n-1)! (当n>1)写成递归函数可以是:float fac(int n){if(n<0) print("错误!");else if(n==0 || n==1) return 1;else return fac(n-1)*n;}然后可以在主函数里这样调用:main(){int a;a=fac(99); //求99的阶乘printf(f%,a); //输出}小结这两个例子是递归的最简单的情况.像汉诺塔,八皇后也是十分经典的递归问题,大家有兴趣可以参考程序设计的书籍.但是和上述的例子的实质是一样的.要注意几个问题:1.递归函数一定要有停止递归的语句,程序不要出现逻辑上的错误. 2.参数的传递体现了递推和问题简化的过程,一般来说内层函数和外层函数的参数是直接有联系的.函数的返回值体现了回推的过程.。
C++练习题一、掌握递归调用：任何有意义的递归调用总是由两部分组成的，即递归公式与递归结束条件。
递归函数设计的一般形式是：函数类型递归函数名f (参数x ){if(满足结束条件)结果=初值；else结果=含f(x-1)的表达式；返回结果；}例题：书P81例4-12，例4-13，二、掌握冒泡排序法算法：如果一个数组b，有n个数，则要进行n-1趟比较，在第一趟中要进行n-1次两两比较，在第j趟中要进行n-j次两两比较，冒泡排序的算法如下边：void bubble ( int b[ ], int n){for ( int i=0; i<n-1;n++ );for ( int j=0;j<n-1-i ; j++);if ( b[j]<b[i] ){int t=b[j];b[j]=b[j+1];b[j+1]=t;}}例题：书P143例7-3三、掌握二维数组的应用例题：书P146例7-4，例7-6四、练习1.C++中两个逻辑常量是什么？（true,false）C++语言和C语言的不同点(C++为面向对象程序设计,C为面向过程程序设计或称结构化程序设计)。
2.C++语言的具有抽象、封装、继承、多态的特点，理解每个特点的意思(课本P3-P4)3.表达式中不同类型的数据进行混合运算时，不同类型数据的转换顺序。
比如10+a+x*y，其中a为float型，x为int型，y为double型，那么整个表达式的值是什么类型？(double型)4.复合的赋值运算符（a+=b、x*=y+8、%=）的用法a+=b 相当于a=a+bx*=y+8 相当于x=x*(y+8)a%=b 相当于a=a%b5.在类中声明一个友元函数的格式？比如viod fun（）函数是类A的友元函数。
友元函数的限定词:friend例: friend viod fun（）6.熟悉三目运算符（？：）(课本P47)、自增（++）自减（--）的用法格式：关系表达式？表达式1：表达式2功能：当关系表达式的值为真，结果为表达式1的值，关系表达式的值为假，结果为表达式2的值例：若有定义”int x=4,y=5;”,则表达式”y>x++?x--:y++”的值为( C )A) 3 B) 4 C) 5D) 6《习题与指导》P5 第27-32题,自增自减: 《习题与指导》P4第17题7.三个循环语言（for、while、do…while）的用法，给定条件后，会判断循环次数。
关于递归的⼀些⼩练习递归什么是递归在程序中, 所谓的递归, 就是函数⾃⼰直接或间接的调⽤⾃⼰.1. 直接调⽤⾃⼰2. 间接调⽤⾃⼰就递归⽽⾔最重要的就是跳出结构. 因为跳出了才可以有结果.所谓的递归就是化归思想递归的调⽤, 写递归函数, 最终还是要转换为⾃⼰这个函数.假如有⼀个函数 f, 如果它是递归函数的话, 那么也就是说函数体内的问题还是转换为 f 的形式.递归思想就是将⼀个问题转换为⼀个已解决的问题来实现function f() {... f( ... ) ...}例⼦: 1, 2, 3, 4, 5, ..., 1001. ⾸先假定递归函数已经写好, 假设是 foo. 即 foo( 100 ) 就是求 1 到 100 的和2. 寻找递推关系. 就是 n 与 n-1, 或 n-2 之间的关系: foo( n ) == n + foo( n - 1 )var res = foo( 100 );var res = foo( 99 ) + 100;3. 将递推结构转换为递归体function foo( n ) {return n + foo( n - 1 );}* 将求 100 转换为求 99* 将求 99 转换为求 98* ...* 将求 2 转换为求 1* 求 1 结果就是 1* 即: foo( 1 ) 是 14. 将临界条件加到递归体中function foo( n ) {if ( n == 1 ) return 1;return n + foo( n - 1 );}练习: 求 1, 3, 5, 7, 9, ... 第 n 项的结果与前 n 项和. 序号从 0 开始求第 n 项的1. ⾸先假定递归函数已经写好, 假设是 fn. 那么第 n 项就是 fn( n )2. 找递推关系: fn( n ) == f( n - 1 ) + 23. 递归体function fn( n ) {return fn( n-1 ) + 2;}4. 找临界条件求 n -> n-1求 n-1 -> n-2...求 1 -> 0求第 0 项, 就是 15. 加⼊临界条件function fn( n ) {if ( n == 0 ) return 1;return fn( n-1 ) + 2;}前n项和1. 假设已完成, sum( n ) 就是前 n 项和2. 找递推关系: 前 n 项和等于第 n 项 + 前 n-1 项的和3. 得到递归体function sum( n ) {return fn( n ) + sum( n - 1 );}4. 找临界条件n == 1 结果为 15. 得到递归函数function sum( n ) {if ( n == 0 ) return 1;return fn( n ) + sum( n - 1 );}练习: 2, 4, 6, 8, 10 第 n 项与前 n 项和第n项function fn( n ) {if ( n == 0 ) return 2;return fn( n-1 ) + 2;}前n项和function sum( n ) {if ( n == 0 ) return 2;return sum( n - 1 ) + fn( n );}练习: 数列: 1, 1, 2, 4, 7, 11, 16, … 求第 n 项, 求前 n 项和.求第 n 项1. 假设已经得到结果 fn, fn( 10 ) 就是第 10 项2. 找递推关系0, 1 => fn( 0 ) + 0 = fn( 1 )1, 2 => fn( 1 ) + 1 = fn( 2 )2, 3 => fn( 2 ) + 2 = fn( 3 )...n-1, n => fn( n-1 ) + n - 1 = fn( n )3. 递归体也就清楚了, 临界条件是 n == 0 => 1function fn( n ) {if ( n == 0 ) return 1;return fn( n-1 ) + n - 1;}如果从 1 开始表⽰, 那么第 n 项为1. 假设已经得到结果 fn, fn( 10 ) 就是第 10 项2. 找递推关系1, 2 => fn( 1 ) + 0 = fn( 2 )2, 3 => fn( 2 ) + 1 = fn( 3 )3, 4 => fn( 3 ) + 2 = fn( 4 )...n-1, n => fn( n-1 ) + n - 2 = fn( n )3. 临界条件 n == 1 => 1前n项和function sum( n ) {if ( n == 0 ) return 1;return sum( n - 1 ) + fn( n );}如果从 0 开始0 1 2 3 4 5 61, 1, 2, 4, 7, 11, 16,如果从 1 开始1 2 3 4 5 6 71, 1, 2, 4, 7, 11, 16,练习: Fibonacci 数列: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …求其第 n 项.递推关系 fn(n) == fn( n- 1) + fn( n - 2)function fib( n ) {if ( n == 0 || n == 1 ) return 1;return fib( n - 1 ) + fib( n - 2 );}阶乘阶乘是⼀个运算, ⼀个数字的阶乘表⽰的是从 1 开始累乘到这个数字. 例如 3! 表⽰1 * 2 * 3. 5! 就是1 * 2 * 3 * 4 * 5. 规定 0 没有阶乘, 阶乘从 1 开始.求 n 的阶乘function foo ( n ) {if ( n == 1 ) return 1;return foo( n - 1 ) * n;}求幂求幂就是求某⼀个数⼏次⽅2*2 2 的平⽅, 2 的 2 次⽅求 n 的 m 次⽅最终要得到⼀个函数 power( n, m )n 的 m 次⽅就是 m 个 n 相乘即 n 乘以 (m-1) 个 n 相乘function power ( n, m ) {if ( m == 1 ) return n;return power( n, m - 1 ) * n;}深拷贝如果要实现深拷贝那么就需要考虑将对象的属性, 与属性的属性, ... 都拷贝过来如果要实现:1. 假设已经实现 clone( o1, o2 ), 将对象 o2 的成员拷贝⼀份交给 o12. 简单的算法, 将 o2 的属性拷贝到 o1 中去function clone( o1, o2 ) {for ( var k in o2 ) {o1[ k ] = o2[ k ];}}3. 找递推关系, 或叫划归为已经解决的问题假设⽅法已经实现, 问⼀下, 如果 o2[ k ] 是对象继续使⽤这个⽅法因此需要考虑的是 o2[ k ] 如果是引⽤类型, 再使⽤⼀次 clone() 函数如果 o2[ k ]不是引⽤类型, 那么就直接赋值function clone( o1, o2 ) {for ( var k in o2 ) {if ( typeof o2[ k ] == 'object' ) {o1[ k ] = {};clone( o1[ k ] , o2[ k ] );} else {o1[ k ] = o2[ k ];}}}复杂实现: clone( o ) -> newObjfunction clone( o ) {var temp = {};for ( var k in o ) {if ( typeof o[ k ] == 'object' ) {temp[ k ] = clone( o[ k ] );} else {temp[ k ] = o[ k ];}}return temp;}请⽤递归实现 getElementsByClassName<div><div>1<div class="c">2</div><div>3</div></div><div class="c">4</div><div>5<div>6</div><div class="c">7</div></div><div>8</div></div>1. 如果实现⼀个⽅法 byClass( node, 'c', list ), 表⽰在某⼀个节点上查找符合 class 属性为 c 的元素2. 在当前元素的⼦元素中查找, 如果有符合要求的, 存储到⼀个数组中3. ⾸先遍历⼦节点, 然后看⼦节点是否还有⼦节点, 如果没有直接判断, 如果有再递归function byClass( node, className, list ) {var arr = node.childNodes;for ( var i = 0; i < arr.length; i++ ) {if ( arr[ i ].className == className ) {list.push( arr[ i ] );}if ( arr[ i ].childNodes.length > 0 ) {byClass( arr[ i ], className, list );}}}。
《C语言程序设计教程》第三版课后习题参考答案C语言程序设计教程第三版课后习题参考答案第一章：C语言概述1.1 C语言的特点答案：C语言是一种通用的、面向过程的程序设计语言，具有高效、简洁、灵活等特点。
它提供了丰富的程序设计元素和功能，适用于各种不同的应用领域。
1.2 C语言程序的基本结构答案：C语言程序由预处理指令、函数声明、函数定义、变量声明和语句组成。
其中，预处理指令用来引入头文件或定义宏，函数声明用来声明函数的名称和参数，函数定义用来实现函数的功能，变量声明用来声明变量的类型和名称，语句用来表达具体的计算过程。
1.3 C语言的数据类型答案：C语言提供了多种数据类型，包括基本类型（整型、浮点型、字符型等）和派生类型（数组、指针、结构体等）。
每种数据类型在内存中占据一定的存储空间，并具有特定的取值范围和操作规则。
1.4 C语言的运算符和表达式答案：C语言支持各种运算符和表达式，例如算术运算符（+、-、*、/等）、关系运算符（>、<、==等）、逻辑运算符（&&、||、!等）等。
通过运算符和表达式可以进行各种数值计算和逻辑判断。
第二章：基本数据类型与运算2.1 整型数据类型答案：C语言提供了不同长度的整型数据类型，包括有符号整型（int、long等）和无符号整型（unsigned int、unsigned long等）。
整型数据类型可以表示整数值，并具有不同的取值范围。
2.2 浮点型数据类型答案：C语言提供了浮点型数据类型（float、double等），用来表示带小数部分的实数值。
浮点型数据可以表示较大或较小的数值，并具有一定的精度。
2.3 字符型数据类型答案：C语言提供了字符型数据类型（char），用来表示单个字符。
字符型数据可以用于表示各种字符（包括字母、数字、符号等）。
2.4 布尔型数据类型答案：C语言不直接支持布尔型数据类型，但可以使用整型数据类型来表示布尔值（0表示假、非零表示真）。
c语言递归编程题递归是一种重要的编程技术，它在许多算法和问题解决方案中发挥着关键作用。
C语言作为一种强大而受欢迎的编程语言，也支持递归。
本文将提供一些C语言的递归编程题，帮助读者了解和练习递归的应用。
题目一：阶乘计算在C语言中，阶乘是一个经典的递归问题。
阶乘定义为正整数n与小于等于n的所有整数的乘积。
请使用递归编写一个函数，计算给定正整数n的阶乘。
解答：```c#include <stdio.h>int factorial(int n) {//递归基，当n等于1时，阶乘为1if (n == 1) {return 1;}//递归调用，计算(n-1)!，然后乘以nreturn n * factorial(n-1);}int main() {int n;printf("请输入一个正整数：");scanf("%d", &n);printf("%d的阶乘为：%d\n", n, factorial(n));return 0;}```以上代码实现了阶乘的递归计算。
通过不断地将问题转化为规模更小的子问题，最终达到基本情况，从而结束递归。
题目二：斐波那契数列斐波那契数列是另一个经典的递归问题。
斐波那契数列的第n个数是前两个数之和，其中第一个和第二个数分别定义为1。
请使用递归编写一个函数，计算第n个斐波那契数。
解答：```c#include <stdio.h>int fibonacci(int n) {//递归基，当n为1或2时，斐波那契数为1if (n == 1 || n == 2) {return 1;}//递归调用，计算前两个数的和return fibonacci(n-1) + fibonacci(n-2);int main() {int n;printf("请输入一个正整数：");scanf("%d", &n);printf("斐波那契数列的第%d个数为：%d\n", n, fibonacci(n));return 0;}```以上代码使用递归的方式计算斐波那契数列的第n个数。
递归调用详解分析递归调用的详细过程递归调用是一种在函数内部调用自身的方法。
当一个函数被调用时，它会在内存中分配栈帧来存储函数的局部变量、参数和返回地址。
在递归调用中，每次调用函数时都会分配一个新的栈帧，这使得函数能够多次重复执行相同的操作。
为了更好地理解递归调用的详细过程，我们可以通过一个经典的例子来进行分析，计算阶乘。
阶乘可以用递归的方式来计算，即n!=n*(n-1)!假设我们调用一个名为 factorial 的函数来计算阶乘，其代码如下：```int factorial(int n)if (n == 0)return 1;} elsereturn n * factorial(n - 1);}```现在我们来详细分析一下调用 factorial(4) 的过程：1. 首先，我们调用 factorial(4)。
由于 n 不等于 0，执行 else分支的代码。
2. 在执行 return 语句之前，需要先计算 factorial(n - 1) 的值。
这时我们需要调用 factorial(3)。
3. 继续重复步骤 2，我们需要调用 factorial(2)。
4. 再次重复步骤 2，我们需要调用 factorial(1)。
5. 重复步骤 2，我们需要调用 factorial(0)。
6. 当 n等于 0 时，执行 if 分支的代码，直接返回 17. 现在我们可以回到步骤 2，计算 factorial(1) * 1 的值，即 1* 1 = 18. 继续回到步骤 3，计算 factorial(2) * 1 的值，即 2 * 1 = 29. 再次回到步骤 4，计算 factorial(3) * 2 的值，即 3 * 2 = 610. 最后回到步骤 1，计算 factorial(4) * 6 的值，即 4 * 6 =24通过以上步骤，我们可以看到递归调用的详细过程。
每次递归调用时，会将当前的参数值n减1，并将下一次递归调用的结果与当前的n相乘，最后返回相乘的结果。
c语言递归试题及答案C语言递归试题及答案1. 问题描述：编写一个C语言函数，使用递归方法计算一个整数n的阶乘。
2. 函数原型：```cint factorial(int n);```3. 递归函数实现：```cint factorial(int n) {if (n <= 1) {return 1;} else {return n * factorial(n - 1);}}```4. 测试代码：```c#include <stdio.h>int factorial(int n);int main() {int n = 5;printf("The factorial of %d is %d\n", n, factorial(n)); return 0;}```5. 答案：当输入为5时，程序输出应为：```The factorial of 5 is 120```6. 问题分析：阶乘函数是一个经典的递归问题。
递归函数`factorial`通过检查参数`n`是否小于等于1来决定是否结束递归。
如果`n`为1或更小，函数返回1，因为1的阶乘是1。
否则，函数调用自身计算`n-1`的阶乘，并将结果乘以`n`。
7. 注意事项：- 递归函数必须有一个明确的退出条件，否则会导致无限递归。
- 递归深度过大时可能会导致栈溢出。
8. 扩展问题：如何使用递归方法计算斐波那契数列的第n项？9. 斐波那契数列递归函数实现：```cint fibonacci(int n) {if (n <= 1) {return n;} else {return fibonacci(n - 1) + fibonacci(n - 2);}}```10. 斐波那契数列测试代码：```c#include <stdio.h>int fibonacci(int n);int main() {int n = 10;printf("The %dth Fibonacci number is %d\n", n, fibonacci(n));return 0;}```11. 斐波那契数列答案：当输入为10时，程序输出应为：```The 10th Fibonacci number is 55```12. 斐波那契数列问题分析：斐波那契数列是一个每一项都是前两项和的序列，定义为：F(0)= 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。
C语言综合练习题（一）一选择题（7分，每小题0.5分）1.设a为整型变量,初值为12,执行完语句 a+=a-=a*a后,a的值是（）。
A 552B 144C 264D -2642.下列标识符中，不能作为合法的C用户定义标识符的是（）。
A a3_b3B voidC _123D IF3.下列整数值中，不正确的八进制或十六进制数值常量是（）。
A 0xcdB -017C -ox123D 0xfdc4.若给定条件表达式(M)?(a++):(a--)，则其中表达式M和（）等价。
A M==0B M=1C M!=1D M!=05.在C语言中，if语句后的一对圆括号中，用以决定分支流程的表达式为（）。
A 只能是逻辑表达式 B只能是关系表达式C 只能是逻辑表达式或关系表达式 D可以是任意表达式6.以下程序的输出结果为（）。
main( ){ char c;int i;for(i=65;i<68;i++){ c=i+32;switch(c){ case ‘a’:printf("%c,",c);break;case ‘b’:case ‘e’:printf("ok,");default: printf("end");}} }A a,ok,endB a,ok,endendC a,ok,end,endD a,ok,ok7.数组名作为实参数传递给函数时，数组名被处理为（）。
A 该数组的长度B 该数组的元素个数C 该数组的首地址D 该数组中各元素的值8.关于return语句，下列正确的说法是（）。
A 可以在同一函数中出现多次B 在主函数中不能出现C 必须在每个函数中出现D 只能在除主函数之外的函数中出现一次9.以下程序的输出结果为（）。
#define A 3#define B(a) (A+1)*amain(){ int x;x=3*A+B(7);printf("x=%d\n",x);}A x=93B x=37C x=60D x=9010.设有以下定义，则以下对变量w的赋值（）是错误的。
