函数和递归.docx

函数和递归.docx

《函数和递归.docx》由会员分享，可在线阅读，更多相关《函数和递归.docx（26页珍藏版）》请在冰点文库上搜索。

函数和递归

第4章函数和递归

【教学内容相关章节】

4.1数学函数4.2地址的指针4.3递归4.4本章小结

【教学目标】

（1）掌握多参数、单返回值的数学函数的定义和使用方法；

（2）学会用typedef定义结构体；

（3）学会用assert宏帮助调试；

（4）理解函数调用时用实参给形参赋值的过程；

（5）学会定义局部变量和全局变量；

（6）理解调用栈和栈帧，学会用gdb查看调用栈并选择栈桢；

（7）理解地址和指针；

（8）理解递归定义和递归函数；

（9）理解可执行文件中的正文段、数据段和BSS段；

（10）熟悉堆栈段，了解栈溢出的常见原因。

【教学要求】

掌握带参函数的调用、赋值过程及函数的返回值，理解地址和指针的概念，理解递归定义和递归函数，理解段的概念。

【教学内容提要】

运用前3章的知识尽管在理论上已经足以写出多数算法程序了，但实际上稍微复杂一点的程序往往由多个函数组成。

函数是“过程式程序设计”的产物，但也产生了局部变量、参数传递方式、递归等诸多新的知识点。

本章淡化例题，重点在于理解最后的语法。

同时，通过请出gdb这一王牌，从根本上帮助读者理解，看清事物的本质。

【教学重点、难点】

教学重点：

（1）掌握多参数、单返回值的数学函数的定义和使用方法；

（2）理解函数调用时用实参给形参赋值的过程；

（3）理解地址和指针；

（4）理解递归定义和递归函数；

（5）理解可执行文件中的正文段、数据段和BSS段；。

教学难点：

贪心算法的基本要素。

【课时安排（共3学时）】

4.1数学函数4.2地址的指针4.3递归

4.4本章小结

（0.5学时）

4.1数学函数

4.1.1简单函数的编写

下面给出一个计算两点欧几里德距离的函数：

doubledist（doublex1,doubley1,doublex2,doubley2）

{

returnsqrt（（x1-x2）*（x1-x2）+（y1-y2）*（y1-y2））;

}

提示4-1：

C语言中的数学函数可以定义成“返回类型函数名（参数列表）{函数体}”，其中函数体的最后一条语句应该是“return表达式；”。

提示4-2：

函数的参数和返回值最好是“一等公民”int或double（注意char是一种特殊的int）。

其他“非一等公民”作为以参数和返回值要复杂一些。

提示4-3：

如果函数在执行的过程中碰到了return语句，将直接退出这个函数，不去执行后面的语句。

相反，如果在执行过程中始终没有return语句，则会返回一个不确定的值。

幸好，-Wall可以捕捉到这一可疑情况并产生警告。

main函数是有返回值的，假设返回值为0。

main函数是整个程序的入口，如果有一个“其他的程序”来调用这个main函数——如操作系统、IDE、调试器，甚至自动评测系统，这个0代表“正常结束”，就是返回给这些调用者的。

在算法竞赛中，除了有特殊规定之外，请总是让它返回0，以免评测系统错误地认为你的程序是异常退出。

提示4-4：

在算法竞赛中，请总是让main函数返回0。

下面给出上述函数的另一种方法：

doubledist（doublex1,doubley1,doublex2,doubley2）

{

doubledx=x1-x2;

doubledy=y1-y2;

returnhypot（dx,dy）;

}

说明：

（1）hypot函数的功能是计算一直角三角形的斜边长度。

（2）函数hypot（x,y）表示根据直角三角形的两直解边长度x和y计算其斜边的长度。

或者是从标点（x,y）到原点的距离，该函数的算法等同于sqrt（x*x+y*y）。

4.1.2使用结构体的函数

由于平面的点坐标（x,y）可以看用一个整体，所以可以定义一个结构体,它的名称是Point，让它包含点的坐标x和y。

structPoint{doublex,y;};

doubledist（structPointa,structPointb）

{

returnhypot（a.x-b.x,a.y-b.y）;

}

提示4-5：

在C语言中，定义结构体的方法为：

“struct结构体名称{域定义};”,注意花括号的后面还有一个分号。

由于上面的定义在所有用到Piont的地方都得写一个“struct”，所以给出一个简洁的写法如下：

typedefstructPoint{doublex,y;}Point;

doubledist（Pointa,Pointb）

{

returnhypot（a.x-b.x,a.y-b.y）;

}

提示4-6：

为了方便，往往用“typedefstruct{域定义}类型名;”的方式定义一个新类型名。

这样，就可以像原生数据类型一样使用这个自定义类型。

4.1.3应用举例

例4-1组合数。

输入非负整数m和n，输出组合数

，其中m≤n≤20。

【分析】

由组合数的公式可知，多次出现阶乘，所以将求阶乘作为一个函数：

程序4-1组合数

#include

intf（intn）

{

inti,m=1;

for（i=1;i<=n;i++）

m*=i;

returnm;

}

intmain（）{

intm,n;

scanf（"%d%d",&m,&n）;

printf（"%d\n",f（n）/（f（m）*f（n-m）））;

return0;

}

注意：

编好程序后，一定要别忘了测试程序。

提示4-7：

即使最终答案在我们选择的数据类型范围之内，计算的中间结果仍然可能溢出。

例4-2孪生素数。

如果n和n+2都是素数，则称它们是孪生素数。

输入m，输出两个数均不超过m的最大孪生素数。

5≤m≤10000。

例如m=20时答案是17、19，m=1000时答案是881、883。

【分析】

被1和它自身整除的、大于1的整数称为素数。

由于要判断n和n+2是否是素数，所以把“判断素数”可以写成一个函数，只需调用这个函数两次就可以了。

这样的“判断一个事物是否具有某一性质”的函数还有一个学术名称——谓词（predicate）。

程序4-2孪生素数

（1）

#include

/*doNOTusethisifxisverylargeorsmall*/

intis_prime（intx）

{

inti;

for（i=2;i*i<=x;i++）

if（x%i==0）return0;

return1;

}

intmain（）

{

inti,m;

scanf（"%d",&m）;

for（i=m-2;i>=3;i--）

if（is_prime（i）&&is_prime（i+2））{

printf（"%d%d\n",i,i+2）;

break;

}

return0;

}

说明：

（1）在is_prime函数的编写中，用到了两上小技巧。

一是只判断不超过sqrt（x）的整数i；二是及时退出：

一旦发现x有一个大于1的因子，立刻返回0（假），只有最后才返回1（真）。

（2）函数的命名应注意做到“见名知意”，即选有含义的英文单词（或其缩写）作为函数名。

例如，“is_prime”取自英文“isisaprime?

”（它是素数吗？

）。

提示4-8：

建议把谓词（用来判断某事物是否具有某种特性的函数）命名成“is_xxx”的形式。

它返回int值，非0表示值，0表示假。

提示4-9：

编写函数时，应尽量保证它能对任何合法参数都能得到正确的结果。

如若不然，应在显著位置标明函数的缺陷，以避免误用。

下面改进之后的版本：

程序4-3孪生素数

（2）

#include

#include

#include

intis_prime（intx）{

inti,m;

assert（x>=0）;//使用断言，防止x<0

if（x==1）return0;

m=floor（sqrt（x）+0.5）;

for（i=2;i<=m;i++）

if（x%i==0）return0;

return1;

}

intmain（）{

inti,m;

scanf（"%d",&m）;

for（i=m-2;i>=3;i--）

if（is_prime（i）&&is_prime（i+2））{

printf（"%d%d\n",i,i+2）;

break;

}

return0;

}

除了特判n==1的情况外，程序中还使用了变量m，一方面避免了每次重复计算sqrt（x），另一方面也通过四舍五入避免了浮点误差。

最后，程序使用了assert.h的assert宏来限制非法的函数调用：

当x>=0不成立时，程序将异常终止，并给出了提示信息。

说明：

（1）断言（assert）的语义如下：

如果表达式的值为0（假），则输出错误消息并终止程序的执行（一般还会出对话框，说明在什么地方引发了assert）；如果表达式为真，则不进行任何操作。

因此，断言失败就表明程序存在一个bug。

（2）C/C++的宏（assert）就是这样的断言，当表达式为假时，调用库函数abort（）终止程序。

（3）程序中可以把assert看成一个在任何系统状态下都可以安全使用的无害测试手段，所以不要把程序中的assert语句删除掉。

（4）如果程序在assert处终止了，并不是说含有该assert的函数有错误，而是调用函数出了差错，assert可以帮助我们追踪到错误发生的原因。

（5）在函数的入口处，建议使用断言来检查参数的有效性（合法性）。

请给assert语句加注释，告诉人们assert语句究竟要干什么。

提示4-10：

编程时合理利用assert宏，将给调试带来很大的方便。

总而言之，在实际的系统中，“一个地方的参数错误就引起整个程序异常退出”是不可取的，在编写和调试算法程序中，assert会“迫使”编写出更高质量的程序。

4.2地址和指针

有时候，我们编程时为了完成某些操作——如交换两个变量，或者需要返回两个甚至更多的值——如解一个二元一次方程组。

4.2.1变量交换

程序4-4用函数交换变量（错误）

#include

voidswap（inta,intb）{

intt=a;a=b;b=t;

}

intmain（）{

inta=3,b=4;

swap（3,4）;

printf（"%d%d\n",a,b）;

return0;

}

说明：

（1）下面来说一下函数调用的过程：

①计算参数的值（若是数学表达式，需要计算）。

程序4-4中函数调用语句swap（a,b）;中的a和b就是实际参数（简称实参），它们的值分别为3和4。

实参可以是常量、变量或表达式。

②把实参赋值给函数声明中的a和b。

函数声明中的a和b称为形式参数（简称形参）。

然后在函数内部完成计算或操作。

注意实参向形参的数据传递是“值传递”，即单向传递，只由实参传给形参，而不能由形参传回来给实参。

（2）下面来说一下几个概念：

①局部变量（localvariable）

函数（包括main函数）的形参和在该函数里定义的变量都被称为该函数的局部变量。

不同的局部变量相互独立，无法访问其他函数的局部变量，也就是说，局部变量只能在定义它的函数内部使用，超出了局部变量的作用域范围，局部变量是无效的。

局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放，其中的值无法保留到下次使用。

②静态局部变量（staticlocalvariable）

有时希望函数中的局部变量的值在函数调用结束后不消失而保留原值，这时就应该指定局部变量为“静态局部变量”，用关键字static进行声明。

静态局部变量在程序整个运行期间都不释放，而局部变量在函数调用结束后即释放。

静态局部变量在编译时赋初值，即只赋初值一次；而对自动变量赋初值是在函数调用时进行，每调用一次函数重新给一次初值，相当于执行一次赋值语句。

如果在定义局部变量时不赋初值的话，则对静态局部变量来说，编译时自动赋初值0（对数值型变量）或空字符（对字符变量）。

而对自动变量来说，如果不赋初值则它的值是一个不确定的值。

静态局部变量在函数调用结束后仍然存在，其它函数是不能引用它们的。

③全局变量（globalvariable）

将变量写在所有函数的外面，这样的变量是全局变量。

全局变量可以在任何时候，由任何函数访问。

如果某局部变量和某个全局变量的名字一样，那么在该局部变量的作用域中，起作用的是局部变量，全局变量被同名的局部变量屏蔽掉了，不起作用。

需要注意的是，全局变量是非常危险的，应该谨慎使用。

提示4-11：

函数的形参和在函数内声明的变量都是该函数的局部变量。

无法访问其他函数的局部变量。

局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将

释放，其中的值无法保留到下次使用。

在函数外声明的变量是全局变量，它们可以被任何函数使用。

操作全局变量有风险，应谨慎使用。

下面就变量的生存期和可见性给出一个例子。

例4-3写出下面程序的运行结果。

#include

inti=1;/*i为全局变量，具有静态生存期*/

voidmain（）

{

staticinta;/*a为静态局部变量，具有全局寿命，局部可见*/

intb=-10;

intc=0;

voidother（）;

printf（"-----MAIN------\n"）;

printf（"i:

%da:

%db:

%dc:

%d\n",i,a,b,c）;

c=c+8;

other（）;

printf（"-----MAIN------\n"）;

printf（"i:

%da:

%db:

%dc:

%d\n",i,a,b,c）;

i=i+10;

other（）;

}

voidother（）

{

staticinta=2;

staticintb;

/*a,b为静态局部变量，具有全局寿命，局部可见，只第一次进入函数进入

函数时初始化*/

intc=10;/*c为局部变量，具有动态生存期，每次进入函数时都初始化*/

a=a+2;i=i+32;c=c+5;

printf（"-----OTHER------\n"）;

printf（"i:

%da:

%db:

%dc:

%d\n",i,a,b,c）;

b=a;

}

解答：

运行结果为如下：

-------Main--------

i:

1a:

0b:

-10c:

0

------Other--------

i:

33a:

4b:

0c:

15

-------Main--------

i:

33a:

0b:

-10c:

8

-------Other-------

i:

75a:

6b:

4c:

15

4.2.2调用栈

调用栈描述的是函数之间的调用关系。

它由多个栈帧（StackFrame）组成，每个栈帧对应着一个未运行完的函数。

栈帧中保存了该函数的返回地址和局部变量，因而不仅能在执行完毕后找到正确的返回地址，还很自然地保证了不同函数的局部变量互不相干——因为不同函数对应着不同的栈帧。

提示4-12：

C语言调用栈（CallStack）来描述函数之间的调用关系。

调用栈由栈帧（StackFrame）组成，每个栈帧对应着一个未运行完的函数。

在gdb中可以用backtrace（简称bt）命令打印所有栈帧信息。

若要用p命令打印一个当前栈帧的局部变量，可以用frame命令选择另一个栈帧。

下面给出用gdb完成上述操作的命令和结果。

（1）第一步：

编译程序。

gcc4-4.c-g

（2）第二步：

运行gdb。

gdba.exe

这样，gdb在运行时会自动装入刚才生成的可执行程序。

（3）第三步：

查看源码。

（gdb）l

这里（gdb）是gdb的提示符，字母l是输入的命令，它是list（列出程序清单）的缩写。

（4）第四步：

加断点并运行。

（gdb）b4

（gdb）r

其中b命令把断点设在了第4行，r命令运行程序，之后碰到了断点并停止。

接下来，查看调用栈。

（5）第四步：

查看调用栈。

（gdb）bt

（gdb）pa

（gdb）pb

（gdb）up

（gdb）pa

（gdb）pb

这一步是关键。

根据bt命令，调用栈中包含两个栈帧：

0#和1#，其中0号是当前栈帧——swap函数，1号是它的“上一个”栈帧——main函数。

使用p命令可以打印变量值。

pa和pb表示查看当前栈帧中变量a和b的值。

up命令表示选择上一个栈帧。

然后用pa和pb查看当前栈帧中变量a和b的值。

最后用q命令退出gdb。

说明：

gdb是GNU开源组织发布的一个强大的UNIX下的程序调试工具。

或许，大家比较喜欢那种图形界面方式的，像VC、BCB等IDE的调试，但如果是在UNIX平台下做软件，会发现gdb这个调试工具有比VC、BCB的图形化调试器更强大的功能。

4.2.3用指针实现变量交换

程序4-4不能实现两个变量的值交换，用指针可以实现两个变量的值交换。

程序4-5用函数交换变量（正确）

#include

voidswap（int*a,int*b）{

intt=*a;*a=*b;*b=t;

}

intmain（）{

inta=3,b=4;

swap（&a,&b）;

printf（"%d%d\n",a,b）;

return0;

}

语句swap（&a,&b）;中变量名前面加&得到的是该变量的地址。

提示4-13：

C语言的变量都是放在内存中的，而内存中的每个字节都有一个称为地址（address）的编号。

每个变量都占有一定数目的字节（可用sizeof运算符获得），其中第一个字节的地址称为变量的地址。

提示4-14：

用int*a声明的变量a是指向int型变量的指针。

赋值a=&b的含义是把变量b的地址存放在指针a中，表达式*a代表a指向的变量，它既可以放在赋值符号的左边（左值），也可以放在右边（右值）。

提示4-15：

千万不要滥用指针，这不仅会把自己搞糊涂，还会让程序产生各种奇怪的错误。

事实上，本书的程序会很少用指针。

4.2.4初学者易犯的错误

一种典型的错误写法是：

voidswap（int*a,int*b）{

int*t=a;a=b;b=t;

}

它交换了swap函数的局部变量a和b（辅助变量t必须是指针。

inta是错误的），但却始终没有修改它们指向的内容，因此main函数中的a和b不会改变。

另一种错误写法是：

voidswap（int*a,int*b）{

int*t;

*t=*a;*a=*b;*b=*t;

}

这个程序去替换程序4-5，可能得到的结果是“43”。

但是它还是错误的，因为t是一个变量（指针也是一个变量，只不过类型是“指针”而已），所以根据规则，它在赋值之前是不确定的。

如果这个“不确定的值”所代表的内存单元恰好是能写入的，那么这个程序将正常工作；但如果它是只读的，程序可能会崩溃。

4.3递归

4.3.1递归的定义和递归函数

1．基本概念

一个函数在它的函数体内调用它自身称为递归调用。

这种函数称为递归函数。

Ｃ语言允许函数的递归调用。

在递归调用中，主调函数又是被调函数。

执行递归函数将反复调用其自身，每调用一次就进入新的一层。

例如：

intf（intx）

{

inty;

z=f（y）;

returnz;

}

本函数是一个递归函数。

但是运行该函数将无休止地调用其自身，这当然是不正确的。

这个递归函数是一个死递归（无限递归，InfiniteRecursion）函数。

为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。

常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。

2．递归函数的构成要素

递归函数必须满足两个条件：

（1）必须有一个终止准则（递归的边界条件、递归的结束条件）；

（2）在每一次调用自己时，必须是（在某种意义上）更接近于解（递推公式或递归方程）；

边界条件与递归方程是递归函数的二个要素。

若没有条件

（1），则递归无从终止；若没有条件

（2），则不是递归。

3．递归调用过程（两个阶段）

（1）递推阶段

将原问题不断地分解为新的子问题，逐渐从未知的向已知的方向推进，最终达到已知的条件，即递归结束条件，这时递推阶段结束。

（2）回归阶段

从已知条件出发，按照“递推”的逆过程，逐一求值回归，最终到达“递推”的开始处，结束回归阶段，完成递归调用。

例4-4用递归法计算n!

。

用递归法计算n!

，阶乘函数f（n）=n!

可定义为：

【分析】

本题是一个递归问题。

下面给出求f（5）的递归过程如下：

（1）递推过程

f（5）=5×f（4）→f（4）=4×f（3）→f（3）=3×f

（2）→f

（2）=2×f

（1）→f

（1）=1×f（0）→f（0）=1

未知------------------------------------------------------------------→已知

（2）回归过程

f（5）=5×f（4）←f（4）=4×f（3）←f（3）=3×f

（2）←f

（2）=2×f

（1）←f

（1）=1×f（0）←f（0）=1

=120=24=6=2=1

未知←-----------------------------------------------------------------已知

对应的程序如下：

程序4-6用递归计算阶乘

#include

intf（intn）{

returnn==0?

1:

f（n-1）*n;

}

intmain（）{

printf（"%d\n",f（3））;

return0;

}

提示4-16：

C语言支持递归——函数可以直接或间接调用自己。

但要注意为递归函数编写终止条件，否则将产生无限递归。

4.3.2C语言对递归的支持

可以借助于gdb来调试程序4-6。

首先用bf命令设置断点——除了可以按行号设置外，也可以直接给出函数名，断点将设置在函数的开头。

可以用r命令运行程序，并在断点处停下来，接下来用s命令单步执行。

每次执行完s指令，都会有一层递归调用终止，直到返回main函数。

事实上，如果在递归调用初期查看调用栈，会发现每次递归调用都会多一个栈帧——和普通的函数调用并没有什么不同。

确实如此，由于使用了调用栈，C语言自然支持了递归。

在C语言的函数中，调用自己和调用其他函数并没有任何本质区别，都是建立新栈帧，传递参数并修改“当前代码行”，在函数体执行完毕后删除栈帧，处理返回值并修改“当前代码行”。

提示4-17：

由于使用了调用栈，C语言支持递归。

在C语言中，调用自己和