第6章函数递推递归(C++版)课程.ppt

第六章 函数和递推递归算法;第一节 函数; 前面我们曾经学习了程序设计中的三种基本控制结构（顺序、分支、循环）。用它们可以组成任何程序。但在应用中，还经常用到子程序结构。 通常，在程序设计中，我们会发现一些程序段在程序的不同地方反复出现，此时可以将这些程序段作为相对独立的整体，用一个标识符给它起一个名字，凡是程序中出现该程序段的地方，只要简单地写上其标识符即可。这样的程序段，我们称之为子程序。 子程序的使用不仅缩短了程序，节省了内存空间及减少了程序的编译时间，而且有利于结构化程序设计。因为一个复杂的问题总可将其分解成若干个子问题来解决，如果子问题依然很复杂，还可以将它继续分解，直到每个子问题都是一个具有独立任务的模块。这样编制的程序结构清晰，逻辑关系明确，无论是编写、阅读、调试还是修改，都会带来极大的好处。 在一个程序中可以只有主程序而没有子程序(本章以前都是如此)，但不能没有主程序，也就是说不能单独执行子程序。 在此之前，我们曾经介绍并使用了C++提供的各种标准函数，如abs(),sqrt()等等，这些系统提供的函数为我们编写程序提供了很大的方便。比如：求sin(1)+ sin(2)+．．．+sin(100)的值。但这些函数只是常用的基本函数，编程时经常需要自定义一些函数。; 例6.1 求：1!+2!+3!+……+10！ #includeiostream using namespace std; int main() { int sum=0; 　　for (int i=1; i=10; i++) 　　　　sum+=js(i); 　　coutsum=sumendl; 　　return 0; } 现在的问题是：C++不提供js(x)这样一个标准函数，这个程序是通不过的。如果是C++的标准函数，我们可以直接调用，如abs(x)，sqrt(x)．．．．．．而C++提供给我们的可供直接调用的标准函数不多。没关系，我们编写自己的函数！;一、函数的定义----【函数】; 数据、影响函数功能的因素或者函数处理的结果作为形参。在被调用函数中的参数被称为形参。 函数中最外层一对花括号“{ }”括起来的若干个说明语句和执行语句组成了一个函数的函数体。由函数体内的语句决定该函数功能。函数体实际上是一个复合语句，它可以没有任何类型说明，而只有语句，也可以两者都没有，即空函数。 函数不允许嵌套定义。在一个函数内定义另一个函数是非法的。但是允许嵌套使用。 函数在没有被调用的时候是静止的，此时的形参只是一个符号，它标志着在形参出现的位置应该有一个什么类型的数据。函数在被调用时才执行，也就是在被调用时才由主调函数将实际参数（简称实参）值赋予形参。这与数学中的函数概念相似，如数学函数： 　　　　　　　　　　f(x)= x 2+x+1 这样的函数只有当自变量被赋值以后，才能计算出函数的值。;2．函数定义的例子 定义一个函数，返回两个数中的较大数。 int max(int x,int y) { return xy?x:y; } 该函数返回值是整型，有两个整型的形参，用来接受实参传递的两个数据，函数体内的语句是求两个数中的较大者并将其返回主调函数。;3．函数的形式 函数的形式从结构上说可以分为三种：无参函数、有参函数和空函数。它们的定义形式都相同。 （1）无参函数 无参函数顾名思义即为没有参数传递的函数，无参函数一般不需要带回函数值，所以函数类型说明为void。 （2）有参函数 有参函数即有参数传递的函数，一般需要带回函数值。例如 int max(int x,int y)函数。 （3）空函数 空函数即函数体只有一对花括号，花括号内没有任何语句的函数。 例如， 函数名（） { } 空函数不完成什么工作，只占据一个位置。在大型程序设计中，空函数用于扩充函数功能。 ; 编写一个阶乘的函数，我们给此函数取一个名字js。 int js(int n) { int s=1; for (int i=1; i=n; ++i) s*=i; return s; } 在本例中，函数名叫js，只有一个int型的自变量n，函数js属int型。在本函数中，要用到两个变量i，s。在函数体中，是一个求阶乘的语句，n的阶乘的值在s中，最后由return语句将计算结果s值带回，js()函数执行结束，在主函数中js()值就是s的值。 在这里，函数的参数n是一个接口参数，说得更明确点是入口参数。如果我们调用函数：js(3)，那么在程序里所有有n的地方，n被替代成3来计算。在这里，3就被称为实