4. 函数和递归

自定义函数和结构体

1. 格式
   • 定义函数
     返回类型 函数名(参数列表){函数体}
     其中函数体的最后一条语句应该是return 表达式;，如果函数无需返回值，则返回类型应写成void。
     main函数也是有返回值的，返回0代表“正常结束”。
   • 定义结构体
     1. 方法一
        struct 结构体名称{ 域定义 };
     2. 方法二
        typedef struct { 域定义; }类型名;
        此方法可使结构体像原生数据类型一样使用这个自定义类型。
2. 计算组合数
   编写函数，参数是两个非负整数n和m，返回组合数=，其中。例如，n=25，m=12时答案为5200300。

   #include<stdio.h>
   
   // 函数定义 
   long long C(int n, int m){
       // 保证m为大的那个数 
       if(m < n-m){
           m = n-m;
       }
       long long ans = 1;
       // 先约分数较大的阶乘 
       for(int i=m+1; i <= n; i++){
           ans *= i;
       }
       // 再除以剩下数的阶乘 
       for(int i =1; i<= n-m; i++){
           ans /= i;
       }
       return ans;
   }
   
   int main() {
       int n, m;
       scanf("%d%d", &n, &m);
       printf("%d", C(n, m));
       return 0;
   }
   

   注意函数的定义一定要定义在main函数之前，因为程序在进行编译时，从上到下进行编译，如果先编译main函数，就会识别不出调用的函数名。
3. 素数判定
   编写函数。参数是一个正整数n，如果它是素数，返回1，否则返回0。

   #include<stdio.h>
   #include<math.h>
   
   // 判断素数 
   int is_prime(int n) {
       // 1 是素数 
       if(n <= 1) return 0;
       // 开方，四舍五入 
       int m = floor(sqrt(n)+0.5);
       //  判断 
       for(int i=2; i<= m; i++){
           if(n%i == 0){
               return 0;
           }
       } 
       return 1;
   }
   
   // 主函数 
   int main() {
       int n;
       scanf("%d", &n);
       if(is_prime(n)){
           printf("1");
       }else{
           printf("0");
       }
       return 0;
   }
   

函数调用与参数传递

1. 形参与实参
   函数的形参和在该函数里定义的变量都称为该函数的局部变量。不同函数的局部变量相互独立，即无法访问其他函数的局部变量。需要注意的是，局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放，其中的值无法保留到下次使用。与此对应的是全局变量。

2. 调用栈（gdb调试）

   • 调用栈描述的是函数之间的调用关系。它由多个栈帧组成，每个栈帧对应着一个未运行完的函数。栈帧中保存了该函数的返回地址和局部变量。
   • 配置gdb环境变量
     DevC++自带gdb.exe，在安装目录中找到路径，如E:\Dev-Cpp\MinGW64\bin，添加到path中。

   • 调试栈

     
     
   

3. 用指针作参数

   • 用函数交换变量

       #include<stdio.h>
     
       void swap(int* a, int* b) {
           int t = *a;
           *a = *b;
           *b = t;
       } 
     
       int main() {
           int a = 3, b = 4;
           swap(&a, &b);
          printf("%d %d\n", a, b);
           return 0;
       }
     

     变量名前面加“&”得到的是该变量的地址。
     *a是指“a指向的变量”，而不仅仅是“a指向的变量所拥有的值”。
     &取地址运算符， *取内容运算符。

4. 初学者易犯错误

   void swap(int* a, int* b){
       int *t;
       *t = *a;
       *a = *b;
       *b = *t;
   }
   

   这个程序错在哪里？
   t是一个指向int型指针，因此*t是一个整数。
   用一个整数作为辅助变量去交换两个整数有何不妥？
   事实上，如果用这个函数去替换上面的程序，很可能会得到“4 3”的正确结果。
   问题在于，t存储的地址是什么？也就是说t指向哪里？因为t是一个变量（指针也是一个变量，只不过类型是“指针”），所以根据规则，它在赋值之前是不确定的。如果这个“不确定的值”所代表的内存单元恰好是能写入的，那么这段程序将正常工作；但如果它是只读的，程序可能崩溃。

5. 数组作为参数和返回值
   如何把数组作为参数传递给函数？

   int sum(int a[]) {
       int ans = 0;
       for(int i = 0; i < sizeof(a); i++){
           ans += a[i];
       }
       return ans;
   }
   

   上面的函数是错误的，因为sizeof(a)无法得到数组的大小。为什么会这样？
   因为把数组作为参数传递给函数时，实际上只有数组的首地址作为指针传递给了函数。

   • 计算数组的元素和

       int sum(int* a, int* b){
           int ans = 0;
           for(int i = 0; i< n; i++){
               ans += a[i]; 
           }
           return ans;
       }
     

     以数组为参数调用函数时，实际上只有数组首地址传递给了函数，需要令加一个参数表示元素个数。除了把数组首地址本身作为实参外，还可以利用指针加减法把其他元素的首地址传递给函数。
     一般的，若p是指针，k是正整数，则p+k就是指针p后面第k个元素，p-k是p前面的第k个元素，而如果p1和p2是类型相同的指针，则p2-p1是从p1到p2的元素个数（不含p2）。
   • 计算左闭右开区间内的元素和

     1. 方法一
     #include<stdio.h>
     #include<math.h>
     
     int sum(int* begin, int* end){
         int n = end - begin;
         int ans = 0;
         for(int i = 0; i < n; i++){
             ans += begin[i];
         } 
         return ans;
     }
     int main()
     {
         int a[] = {1, 2, 3, 4, 5};
         printf("%d \n", sum(a, &a[3]));
         return 0;
     }
     
     2. 方法二
     #include<stdio.h>
     #include<math.h>
     
     int sum(int* begin, int* end){
       int *p = begin;
       int ans = 0;
       for(int *p = begin; p!= end; p++){
             ans += *p;
       }
       return ans;
     }
     int main()
     {
       int a[] = {1, 2, 3, 4, 5};
       printf("%d \n", sum(a, &a[3]));
       return 0;
     }
     

递归

1. 递归定义
   递归的定义如下：
   递归： 参见“递归”
   原来递归就是“自己用到自己”的意思。
2. 递归函数
   数学函数也可以递归定义。例如，阶乘函数可以定义为:
   
   对应程序如下：

   #include<stdio.h>
   
   int f(int n){
       return n == 0 ? 1: f(n-1)*n;
   }
   int main() {
       printf("%d\n",f(3));
       return 0;
   }
   

   C语言支持递归，即函数可以直接或间接地调用自己。但要注意为递归函数编写终止条件，否则将产生无限递归。
3. C语言对递归的支持
   • 由于使用了调用栈，C语言支持递归。在C语言中，调用自己和调用其他函数没有本质区别。
4. 段错误与栈溢出
   • “段”是指二进制文件内的区域。

   • 在gcc生成的可执行文件中，正文段（Text Segment） 用于存储指令，数据段（DataSegment）用于存储已初始化的局部变量，BSS段（BSS Segment）用于存储未赋值的全局变量所需的空间。

     
     
   • 每次递归调用都需要往调用栈里增加一个栈帧，久而久之就越界了。这种情况叫做栈溢出。
   • 调用栈并不储存在可执行文件中，而是在运行时，程序会动态创建一个堆栈段，里面存放着调用栈，因此保存着函数的调用关系和局部变量。
   • 那么栈空间究竟有多大？
     在Linux中，栈大小并没有存储在可执行程序中，只能用ulimit命令修改；在windows中，栈大小存储在可执行程序中，用gcc编译时可以通过-W1,--stack=<byte count>指定。
   • 现在理解了在介绍数组时，建议“把较大的数组放在main函数外”，是因为，局部变量也是放在堆栈段的。栈溢出不一定是递归调用太多，也可能是局部变量太大。只要总大小超过了允许的范围，就会产生溢出。