函数与递归

函数的定义

子程序

库函数

如同Python的库，轮子

C Library中的一些函数

IO函数（输入输出函数）
字符串操作函数
字符操作函数
内存操作函数
时间/日期函数
数学函数
其他库函数

使用库函数，必须引用相应的头文件<xxx.h>

自定义函数

构成

和库函数一样，有函数名、返回值类型、函数参数

ret_type fun_name(para1, *)
{
    statement;语句项
}
/*ret_type - 返回类型
  fun_name - 函数名
  para1 - 函数参数
*/

函数的参数

形式参数

函数名后的变量
形参，当函数调用完后会被销毁只在函数中有效

实际参数

真实传递给函数的参数
实参可以是：常量、变量、表达式、函数等它是实际的量，有确定的值

当实参传给形参时，形参其实是实参的一份临时拷贝。对形参的改变是不会影响实参的。

函数的调用

当需要对变量进行直接操作时，往往考虑传址调用。

传值调用

函数的形参和实参分别占有不同内存块，对形参的修改不会影响实参

#include<stdio.h>

void Swap1(int x, int y)//形参
{
    int tmp = x;
    x = y;
    y = tmp;
}
//以上的x，y有自己的空间
int main()
{
    int a = 10;
    int b = 20;
    printf("a=%d,b=%d\n",a,b);//10，20
    Swap1(a,b);//实参
    printf("a=%d,b=%d\n",a,b);//10,20
    return 0;
}

传址调用

将外部变量的地址传入函数，建立真正的联系

#include<stdio.h>

void Swap2(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

int main()
{
    int a = 10;
    int b = 20;
    printf("a=%d,b=%d\n",a,b);//10,20
    Swap2(&a,&b);
    printf("a=%d,b=%d\n",a,b);//20,10
    return 0;
}

函数：传入的数组？

实现二分查找

#include<stdio.h>

int binsry_search(int arr[], int k)
{
    int sz = sizeof(arr)/sizeof(arr[0]);//error
    int left = 0;
    int right = sz-1;
    
    while (left<=right)
    {
        int mid = (left+right)/2;
        if (arr[mid]<k)
            left = mid+1;
        else if (arr[mid]>k)
            right = mid-1;
        else
            return mid;
    }
    return -1;
}

int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int k = 7;
    int ret = binary_search(arr,k);
    if (-ret)
        printf("找不到指定的数字\n");
    else
        printf("找到了，下标是：%d\n",ret);
    return 0;
}

第五行int sz = sizeof(arr)/sizeof(arr[0]); 对于传入函数的数组，实际传入的只是数组第一个元素的地址。因此不能求得元素个数。

拿到外面计算

#include<stdio.h>

int binary_search(int arr[], int k, int sz)
{
    int left = 0;
    int right = sz-1;
    
    while (left<=right)//= - 同时等于
    {
        int mid = (left+right)/2;//中间元素的下标
        if (arr[mid] < k)
            left = mid+1;
        else if (arr[mid] > k)
            right = mid-1;
        else
            return mid;
    }
    return -1;
}

int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int k = 7;
    int sz = sizeof(arr)/sizeof(arr[0]);
    int ret = binary_search(arr,k,sz);
    if (ret == -1)
        printf("找不到指定的数字\n");
    else
        printf("找到了，下标是：%d\n",ret);
    return 0;
}

函数的嵌套调用和链式访问

函数之间的有机结合

嵌套调用

在函数中调用另一个函数

链式访问

把一个函数的返回值作为另外一个函数的参数

#include<stdio.h>

int main()
{
    printf("%d\n",printf("%d\n",printf("%d\n",43)));
    return 0;
}
//4321

printf()的返回值是打印的字符的个数。

函数的声明和定义

//函数声明
int Add(int, int);//也可以加上变量名

//主函数
int main()
{
    int a = 10;
    int b = 20;
    //函数调用
    int sum = Add(a, b);
    printf("%d",sum);
}

//函数的定义
int Add(int x, int y)
{
    int z = x+y;
    returnn z;
}

函数声明在使用之前函数在主函数前就不用声明

函数声明在.h文件中函数定义在.c文件中和在一块儿叫模块

然后引用头文件就行了：#include "xxx.h"

用双引号

.h文件：

#ifndef _ADD_H_//如果未定义
#define _ADD_H_

//函数声明
int Add(int, int);

#endif

函数递归

什么是递归

函数调用自身的方法（recursion）（大事化小）

递归的两个必要条件

存在限制条件，即边界条件，满足时则不继续
每次递归则越来越接近边界条件，即收敛

无休止的调用会造成Stack overflow：栈溢出

eg1: 打印数字

void print_num(int n)
{
    if (n>9)               //递归边界
        print_num(n/10);   //递归
    printf("%d ",n%10);
}

eg2:字符串长度（无临时变量）

//有临时变量
int my_strlen_1(char* str)
{
    int count = 0;
    while (*str != '\0')
    {
        count++;   //计数器加一
        str++;     //指针向后移动
    }
    return count;
}

//无临时变量
int my_strlen_2(char* str)
{
    if (*str != '\0')//边界条件
        return 1+mystrlen_2(str+1);//函数递归
    else
        return 0;
}

TDD - 测试驱动开发先设计函数在主函数中的实际使用，然后再去实现函数。

递归与迭代

递归与循环算法是殊途同归的
而递归有时会有大量的重复计算

eg：

求解第n个斐波那契数（不考虑溢出）

//递归算法 - 大量重复计算
int Fib1(int n)
{
    if (n<=2)
        return 1;
    else
        return Fib(n-1) + Fib(n-2);//无法计算较大的n
}

//循环算法 - 计算迅速
int Fib2(int n)
{
    int a=1,b=1,c=1;
    while (n>2)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}

递归深度

递归函数f，第一次进去认为是深度是1。以后从深度为n的f中再调用用f(直接或者间接)，这个被调用f的深度为n+1; 整个f最大的深度为递归深度。

「C 语言」3 函数与递归