C语言笔记-3:函数与递归

2021-02-07
1693字
4分钟
C

C语言笔记-3:函数与递归

函数与递归

函数的定义

子程序

分类

  1. 库函数
  2. 自定义函数

库函数

如同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:栈溢出 Stack

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最大的深度为递归深度

Avatar
Zhang.Mathias 巧者劳而智者忧,无能者无所求,饱食而遨游,泛若不系之舟