本章主要要掌握函数的基本使用和递归
目录：
- 函数是什么
- 库函数
- 自定义函数
- 函数参数
- 函数调用
- 函数的嵌套调用和链式访问
- 函数的声明和定义
- 函数递归
一、函数是什么
C语言中的函数的定义是：子程序
- 子程序是一个大型程序中的某部分代码，由一个或多个语句块组成。它负责完成某项特定的任务，而且相较于其他代码，具备相对独立性。
- 一般会有输入参数并有返回值，提供对过程的封装和细节的隐蔽，这些代码通常被集成为软件库
C语言中函数的分类：
- 库函数
- 自定义函数
二、库函数
为什么会有库函数？
基础功能，会被频繁使用，为了提高工作效率，所以C语言的基础库中提供了一系列类似的库函数，方便程序员进行软件开发。
1.怎么学习库函数
可以参考这些网站：
www.cplusplus.com
查询工具：
MSDN(Microsoft Developer Network）
www.cplusplus.com
http://en.cppreference.com
http://zh.cppreference.com（中文版）
使用文档来学习库函数步骤
举例1：学习函数strcpy
int main()
{
char arr1[20]={0};//目标
char arr2[ ]="hello bit";//源码
strcpy(arr1,arr2);//将源码的字符串拷贝给目标
printf("%s",arr1);//打印arr1这个字符串 %s - 以字符串的格式来打印
return 0;
}
//输出结果：
举例2：学习函数memset
int main()
{
char arr[]="hello bit";
memset(arr, 'x', 5);//将arr数组中前五个字符填充成x
printf("%s\n",arr);
return 0;
//结果输出：xxxxx bit
}
2.C语言常用库函数
- IO函数（即输入/输出函数：printf、scanf、getchar、putchar）
- 字符串操作函数（strcmp、strlen）
- 字符操作函数（toupper）
- 内存操作函数（memcpy、memcmp、memset）
- 时间/日期函数（time）
- 数学函数（sqrt、pow）
- 其他库函数
三、自定义函数
自定义函数和库函数一样，有函数名，返回类型和函数参数。但不一样的是，这些要我们自己去设计。
注意：设计函数是一定要保证函数的功能足够单一，如果函数功能冗杂，会导致使用者应用方面变窄，不易于调用
1.函数的组成
ret_type fun_nume(para1, para2 , ...)
{
statement;//语句块
}
// ret_type 返回类型
// fun_name 函数名
// paral 函数参数
\ ******* 举例 ******* \
1.写出一个函数可以找出两个整数中的最大值
函数的return只能返回一个值
get_max(int x, int y)
{
int z = 0;
if (x > y)
z = x;
else
z = y;
return z;//返回z -返回较大值
}
int main()
{
int a = 10;
int b = 20;
//函数调用
int max = get_max(a, b);
printf("max=%d\n", max);
return 0;
}
- 写一个函数可以交换两个整形变量的内容
临时变量的作用：
/***************出问题的代码*******************/
//函数返回类型的地方写出：void,表示这个函数不返回任何值，也不需要返回值
void Swap(int x, int y)
{
int z = 0;//临时变量
z = x;
x = y;
y = z;
}
int main()
{
int a = 10, b = 20;
//写一个函数，交换2个整型变量的值
printf("交换前：a=%d b=%d\n", a, b);
Swap(a, b);
printf("交换后：a=%d b=%d\n", a, b);
return 0;
}
//输出结果：
//交换前：a=10 b=20
//交换后：a=10 b=20
上串代码并没有实现应有的功能
原因是：a、b变量各自有各自所占的内存（空间），将a、b的值传给Swap函数，并不会连同地址传过去，Swap函数中x、y接过值后进行计算，计算完后x、y的值发生变化，并将值传给了x、y各自所在的内存，并没有影响到a、b，所以a，b的值并没有变化，所以最终没有达到交换的效果
更通俗的解释：形参实例化之后其实相当于实参的一份临时拷贝
解决办法：用指针
先简单复习指针的概念：
int main()
{
int a=10;//a占8个字节的空间（64位系统）
int* pa = &a;//&是取地址符号，将a的地址赋给pa，
//pa就是一个指针变量，a是整型int，因此pa也是整型，为pa*
*pa=20;//对pa解引用，那么*pa就是a
printf("%d\n,a);
return 0;
}
//输出结果：20
正确代码如下：
//正确代码是指针将自建函数和主函数联系了起来
//函数返回类型的地方写出：void,表示这个函数不返回任何值，也不需要返回值
void Swap(int* pa, int* pb)//a、b将地址传给指针变量pa、pb
{
int z = 0;//临时变量
z =*pa;//*pa就是a
*pa= *pb;
*pb=z;
}
int main()
{
int a = 10, b = 20;
//写一个函数，交换2个整型变量的值
printf("交换前：a=%d b=%d\n", a, b);
Swap(&a, &b);//将a、b的地址给函数Swap的函数参数
printf("交换后：a=%d b=%d\n", a, b);
return 0;
}
//输出结果：
//交换前：a=10 b=20
//交换后：a=10 b=20
四、函数的参数
- 实际参数（实参）：
真实传给函数的参数，叫实参。实参可以使：常量、变量、表达式、函数等。无论实参是何种类型的量，在进行函数调用时，他们都必须有确定的值，以便把这些值传送给形参 - 形式参数（形参）：
形式参数是指函数名后括号中的变量，因为形式参数只有在函数被调用的过程中才实例化（分配内存单元），所以叫形式参数。形参当函数调用完成之后就自动销毁了。因此形参只在函数中有效。
形参和实参的名字可以相同，也可以不同
上面get_max和Swap函数中的x，y，px，py都是形式参数。在main函数中传给get_max的a，b和传给Swap函数的&a，&b是实际参数
五、函数的调用：
1.传值调用
函数的形参和实参分别占有不同的内存块，对形参的修改不会影响到实参。
2.传址调用
- 传址调用是把函数外部创建变量的内存地址传递给函数参数的一种调用函数的方式。
- 这种传参方式可以让函数和函数外边的变量建立起真正的联系，也就是函数内部可以直接操作函数外部的变量
3.练习
（1）写一个函数可以判断一个数是不是素数
//法一：2~n-1挨个判断
//判断100~200之间的素数
int is_prime(int n)
{
//2~n-1之间的数
int j = 0;
for (j = 2;j < n;j++)
{
if (n % j == 0)
return 0;//能够被整除则不是素数
// else
// return 1;//错误，因为2~n-1之间所有的数都不能被整除才是素数
}
return 1;
}
int main()
{
int i = 0;
int count = 0;//记录有几个素数
for (i = 100;i <= 200;i++)
{
//判断i是否为素数
if (is_prime(i) == 1)
{
count++;
printf("%d ", i);
}
}
printf("\n一共有%d个素数\n", count);
return 0;
}
//法二：优化版
//m=a*b//m可以看成两个因子的相乘
//a和b中一定有一个数是≤√m的
//例如：16=4*4=2*8，其中4和2都是≤√16=4的
//所以我们只要去检测√m前的数就可以了
#include <math.h>
int is_prime(int n)
{
//2~n-1之间的数
int j = 0;
for (j = 2;j <=sqrt( n);j++)//j要写成<=sqrt(n),不能写成<，因为平方数没有进循环判断就返回1了
{
if (n % j == 0)
return 0;//能够被整除则不是素数
// else
// return 1;//错误，因为2~n-1之间所有的数都不能被整除才是素数
}
return 1;
}
//主函数不需要做改变因此省略
（2）写一个函数判断一年是不是闰年
//判断一年是不是闰年
//是4的倍数且不是100的倍数是闰年或者是400的倍数是闰年
int is_RunNian(int k)//一个函数如果不写返回类型，默认返回int
{
if ((k % 4 == 0 && k % 100 != 0) || (k % 400 == 0))
{
return 1;
}
return 0;
}
int main()
{
int year = 0;
scanf("%d", &year);
if (is_RunNian(year) == 1)
{
printf("%d是闰年\n", year);
}
else
printf("%d不是闰年\n", year);
return 0;
}
//法二：更简洁的写法
int is_RunNian(int k)
{
return ((k % 4 == 0 && k % 100 != 0) || (k % 400 == 0));//直接返回括号的内容，括号内为真就会默认返回1，为假默认返回0
}
（3）写一个函数，实现一个整型有序数组的二分查找
int binary_search(int a[], int k,int s)//形参和实参的名字可以相同，也可以不同
//a[]中为什么不填大小？因为数组arr传参，只传了首元素的地址，所以填大小没有意义
{
int left = 0;
int right = s - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (a[mid] > k)
{
right = mid - 1;
}
else if (a[mid] < k)
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;//找不到
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int key = 7;
int sz = sizeof(arr) / sizeof(arr[0]);//arr数组中有sz个元素
//找到了就返回找到的位置的下标
//找不到就返回-1（不返回0的原因是，元素1的下标为0）
//数组arr传参，实际传递的不是数组的本身
//仅仅传过去了数组首元素的地址（本质上数组传参就是在传址）
int ret=binary_search(arr,key,sz);//在arr数组的sz个元素中找key
if (-1 == ret)
{
printf("找不到\n");
}
else
{
printf("找到了，下标是：%d\n", ret);
}
return 0;
}
错误示范：错误原因在上面代码中已介绍
//error
int binary_search(int a[], int k)
{
int sz=sizof(a)/sizof(a[0]);//错误，因为实参只传给a[]一个首元素的地址，因此求出的sz是错误的
int left=0;
int right=sz-1;
//下面代码与上串代码相同，故省略
（4）写一个函数，每调用一次这个函数，就会将num的值增加1
void Add(int* p)
{
(* p)++;
}
int main()
{
int num = 0;
Add(&num);//只有num的地址给Add函数，操作后Add，num的值才能改变
printf("%d\n", num);//1
Add(&num);
printf("%d\n", num);//2
Add(&num);
printf("%d\n", num);//2
return 0;
}
六、 函数的嵌套调用和链式访问
1.嵌套调用
函数是不可以嵌套定义的，但是函数可以嵌套调用
void new_line()
{
printf("haha\n");
}
void therr_line()
{
int i=0;
for(i=0;i<3;i++)
{
new_line();
}
}
int main()
{
therr_line();
return 0;
}
//输出结果：
//haha
//haha
//haha
2.链式访问
把一个函数的返回值作为另外一个函数的参数。
//举例1
#include <string.h>
int main()
{
int len = strlen("abc");
printf("%d\n", len);
//链式访问
printf("%d\n", strlen("abc"));
return 0;
}
//举例2
//strcpy函数是将源字符串拷贝到目的地
//而这个函数的返回值是目的地的起始地址，它的返回类型是指针
int main()
{
//以前是这样写的
char arr1[20] = {0};
char arr2[] = "bit";
strcpy(arr1, arr2);
printf("%s\n", arr1);
//由于strcpy函数的返回值是目的地的起始地址
//因此可以用链式访问取得同样的效果
printf("%s\n", strcpy(arr1, arr2));
return 0;
}
//举例3
int main()
{
printf("%d",printf("%d",printf("%d",43)));
return 0;
}
//输出结果：4321
//因为最内层函数会打印43，43是两个字符，然后会返回给中间那层函数一个2，所以中间那层函数打印2，返回1，最外层函数则打印1
七、 函数的声明和定义
1.函数声明：
- 告诉编译器有一个函数叫什么，参数是什么，返回类型是什么。但是具体是不是存在，对于函数声明来说无关紧要。
- 函数的声明一般出现在函数的使用之前。要满足先声明后使用。
- 函数的声明一般要放在头文件（.h）中，函数的定义放在对应的.c文件中
2.函数定义
函数的定义是指函数的具体实现，交代函数的功能实现。
见上图，如果函数定义了，但是没有声明，并且函数定义也没在函数使用的前面，则会出现编译器找不到这个函数的错误情况。
在真正的应用中，函数的声明和定义是要分文件写的
例如：
test.h的内容放置函数的声明
#ifndef _TEST_H_
#define _TEST_H_
//函数的声明
int Add(int x,int y);
#endif _TEST_H_
test.c的内容放置函数的实现
#include "test.h"
//函数Add的实现
int Add(int x,int y)
{
return x+y;
}
这种分文件的书写形式，在三子棋和扫雷的时候，会进一步讲授。
八、函数递归
1. 什么是递归？
程序调用自身的编程技巧称为递归（ recursion ）。递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可以描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的主要思考方式在于：把大事化小
2. 递归的两个必要条件（注意：这两个条件缺少，必错，全有，不一定对）
(1). 存在限制条件，当满足这个限制条件的时候，递归便不再继续。（比如举例1中的if (n > 9)）
(2). 每次递归调用之后越来越接近这个限制条件。（比如举例1中的n/10）
3. 写递归代码应注意：
1. 不能死递归，要有跳出条件，每次递归逼近跳出条件
2. 递归层次不能太深，过深会导致栈溢出
/*************** 简单小例子 **************/
5. 死递归造成栈溢出
int main()
{
printf("haha\n");
main();//自己调用自己
return 0;
//输出结果：死循环haha
}
但这其实是个失败的例子，真正写递归的时候不能这样写，运行一段时间后就会报错
6. 递归的两个必要条件都满足仍然程序出错举例
栈溢出：
一个内存被划分为三个区：栈区、堆区、静态区
递归的时候，每调用一次就会分配一个空间，当最深层那个返回值后就开始销毁，然后逐层销毁，完成递归，但是如果递归层次过深，栈区都填满了，还没有结束，所以无法销毁，最终就会栈溢出。
3.举例
（1）接收一个整型值（无符号），按照顺序打印它的每一位。例如：输入：1234，输出1 2 3 4.
讲解：
模十得到一位，除十去掉一位，但是拿到每一位是倒着拿的，怎么正着拿呢？
用递归！
每次拿出来一位，多次递归后就全拿出来了
void print(unsigned int n)//为什么用void,因为只用吧字符打印到屏幕上，不需要返回值
{
if (n > 9)//如果这个数是一位以上
{
print(n / 10);//n/10是去掉一位，将去掉一位的数再传给print
}
printf("%d ", n % 10);//n%10是得到一位
}
int main()
{
unsigned int num = 0;
scanf("%u", &num);// %u是无符号整型
//递归 - 函数自己调用自己
print(num);//print函数可以打印参数部分数字的每一位
return 0;
}
分析过程：
（2）编写函数，不允许创建临时变量，求字符串的长度
//如果用库函数中的strlen函数就可以实现这个功能，所以我们其实要模仿一下这个函数
#include <string.h>
int main()
{
char arr[] = "bit";
//对于arr数组来说，其实是有四个元素[b] [i] [t] [\0]
//但是\0不算在字符串长度中
printf("%d\n", srtlen(arr));
return 0;
}
//没用递归时的实现思路
int my_strlen(char* str)//arr是数组名，数组名相当于首元素地址，首元素是b，是字符，因此函数参数用字符指针
//因为printf要打印整型值，所以函数的返回值要设成int
{
int count = 0;//记录字符串长度
while (*str != '\0')//如果该字符不是\0，说明这个字符串还没完
{
count++;//记录长度+1
str++;
}
return count;//跳出循环，说明已经读取完整串字符串，此时的count就是字符串的长度
}
int main()
{
char arr[] = "bit";
//模拟实现一个strlen函数
printf("%d\n", my_strlen(arr));
return 0;
}
用递归的思路：由上面的代码可以知道，我们可以用指针str很容易得到数组arr的首元素地址，然后我们就可以判断这个字符是不是\0，如果不是，那就可以变成1+my_strlen（），然后继续递归，直到找到\0递归结束。
int my_strlen(char* str)
{
if (*str != '\0')//注意str要解引用，这样就是地址所指向的字符了
return 1 + my_strlen(str + 1);//str+1是下一个数组元素地址
else
return 0;//如果第一个元素就是\0,则字符串长度就是0
}
int main()
{
char arr[] = "bit";
//模拟实现一个strlen函数
printf("%d\n", my_strlen(arr));
return 0;
}
过程讲解：
4.递归与迭代
（1） 求n的阶乘。（不考虑溢出）
//循环的方法
int main()
{
int n = 0;
scaf("%d", &n);
int i = 0;
int ret = 1;
//迭代
for (i = 1;i <= n;i++)
{
ret = ret * i;
}
printf("%d\n", ret);
return 0;
}
//递归
int Fac(int n)
{
if (n <= 1)
return 1;
else
return n * Fac(n - 1);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fac(n);
printf("%d\n", ret);
return 0;
}
//有一些功能可以使用迭代的方式实现，也可以使用递归的方式实现
（2）求第n个斐波那契数。（不考虑溢出）
斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……。在数学上这样定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
//递归可以求解，但是效率太低
int Fib(int n)
{
if (n <= 2)
{
return 1;
}
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
但是这个方法会发现效率太低，因为进行了大量的重复计算！
用迭代的方法可以减少重复计算：
//用迭代的方法
int Fib(int n)
{
int a = 1, b = 1, c = 0;
while (n > 2)//看上图，n>2时才能用此方法
{
c = a + b;//这个数等于上两个数相加
a = b;
b = c;
n--;//一共算几次
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
（3）提示
- 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
- 但是这些问题的迭代实现往往比递归实现效率高，虽然代码的可读性稍微差些。
- 当一个问题相当复杂，难以用递归实现时，此时递归实现的简洁性便可以补偿它所带来的运行时的开销。
（4）函数递归的几个经典题目（自主研究）：
- 汉诺塔问题
- 青蛙跳台阶问题
本文含有隐藏内容，请 开通VIP 后查看