本章主要掌握函数的基本使用和递归。
函数是什么？
函数是一个大型程序中的某部分代码， 由一个或多个语句块组成。它负责完成某项特定任务，而且相较于其他代码，具备相对的独立性。
C语言中函数分类：
- 库函数
- 自定义函
库函数
为什么会有库函数？
- 我们知道在我们学习C语言编程的时候，总是在一个代码编写完成之后迫不及待的想知道结果，想把这个结果打印到我们的屏幕上看看。这个时候我们会频繁的使用一个功能：将信息按照一定的格式打印到屏幕上（printf）。
- 在编程的过程中我们会频繁的做一些字符串的拷贝工作（strcpy）。
- 在编程是我们也计算，总是会计算n的k次方这样的运算（pow）。
像上面我们描述的基础功能，它们不是业务性的代码。我们在开发的过程中每个程序员都可能用的到，为了支持可移植性和提高程序的效率，所以C语言的基础库中提供了一系列类似的库函数，方便程序员进行软件开发。
那怎么学习库函数呢？
简单的总结，C语言常用的库函数都有：
IO函数 (printf, scanf, getchar, putchar,…)
字符串操作函数 (strlen,strcpy,…)
字符操作函数 (tolower, toupper,…)
内存操作函数 (memcpy, memset, memmove, memcmp,…)
时间/日期函数 (time,…)
数学函数 (pow, abs, sqrt,…)
其他库函数
对于库函数的学习，我们参照文档（http://www.cplusplus.com）
strcpy
char * strcpy ( char * destination, const char * source );
把source指向的字符串内容拷贝destination指向的空间中，’\0’也要拷贝；
参数：
destination:目标空间的起始地址， 类型为char*
source： 要拷贝字符串的起始地址， 类型为const char *
返回值：destination：目标空间的起始地址。
#include <stdio.h>
#include <string.h>
int main()
{
//char arr1[20] = {0};//目标空间
char arr1[20] = "xxxxxxxxxxx";//目标空间
char arr2[] = "hello";
//strcpy(arr1,arr2);
char* ret = strcpy(arr1,arr2);
//printf("%s\n", arr1);
printf("%s\n", ret);
return 0;
}
目标空间要比待拷贝的字符串空间要大，否则会报错。
'\0’是字符串的结束标志，不算作字符串的长度，但是占一个字节空间。
memset
void * memset ( void * ptr, int value, size_t num );
设置内存块，把ptr指向的空间的前num个字节填充成value
参数：
ptr：要设置的内存块的起始地址
num：要填充的字节个数
value：要填充的字符
返回值：ptr
void*类型的指针可以接收任何类型的指针，“万能指针”。
//memset
//内存设置:以字节为单位进行设置
int main()
{
char arr[] = "hello bit";
char* ret = (char*)memset(arr,'x',5);
printf("%s",arr);//xxxxx bit
return 0;
}
int main()
{
int arr[10] = {0};
memset(arr,1,4 * sizeof(int));
return 0;
}
数组元素是连续存储的，假设小端存储，低权值位存储在低地址
注： 但是库函数必须知道的一个秘密就是：使用库函数，必须包含#include 对应的头文件。
这里对照文档来学习上面几个库函数，目的是掌握库函数的使用方法。
可参考网站：
http://www.cplusplus.com
http://en.cppreference.com
自定义函数
很多功能库函数函数并不能满足，所以更加重要的是自定义函数。自定义函数和库函数一样，有函数名，返回值类型和函数参数。 但是不一样的是这些都是我们自己来设计。
函数的组成：
ret_type fun_name(para1, * )
{
statement;//语句项
}
//ret_type 返回类型
//fun_name 函数名
//para1 函数参数
练习：写一个函数可以找出两个整数中的最大值.
#include <stdio.h>
//get_max函数的设计
int get_max(int x, int y)
{
return (x>y)?(x):(y);
}
int main()
{
int num1 = 10;
int num2 = 20;
int max = get_max(num1, num2);
printf("max = %d\n", max);
return 0;
}
练习：写一个函数可以交换两个整形变量的内容。
代码1：
void swap(int x, int y)
{
//不能实现交换功能
int z = 0;
z = x;
x = y;
y = z;
}
int main()
{
int a = 10;
int b = 20;
printf("交换前：a = %d b = %d\n",a,b);
//函数
swap(a,b);
printf("交换后：a = %d b = %d\n",a,b);
return 0;
}
代码1并没有实现交换两个整型变量的内容，这种传参方式是传值调用，实参传递给形参的时，形参是实参的一份临时拷贝，形参和实参之间并没有任何的联系。
代码2：
void Swap(int* px, int* py)
{
int z = 0;
z = *px;
*px = *py;
*py = z;
}
int main()
{
int a = 10;
int b = 20;
printf("交换前：a = %d b = %d\n",a,b);
//函数
Swap(&a,&b);
printf("交换后：a = %d b = %d\n",a,b);
return 0;
}
代码2使用指针，能够实现交换两个整型变量的功能，这种调用方式是传址调用。
函数内部需要改变函数外面变量的值，那么就传递地址；如果函数内部不需要改变函数外面变量的值，传递值。
函数的参数
实际参数（实参）：
真实传给函数的参数，叫实参。实参可以是：常量、变量、表达式、函数等。无论实参是何种类型的量，在进行函数调用时，它们都必须有确定的值，以便把这些值传送给形参。
形式参数（形参）：
形式参数是指函数名后括号中的变量，因为形式参数只有在函数被调用的过程中才实例化（分配内存单元），所以叫形式参数。形式参数当函数调用完成之后就自动销毁了。因此形式参数只在函数中有效。
函数的调用
传值调用
函数的形参和实参分别占有不同内存块，对形参的修改不会影响实参。
传址调用
传址调用是把函数外部创建变量的内存地址传递给函数参数的一种调用函数的方式。这种传参方式可以让函数和函数外边的变量建立起正真的联系，也就是函数内部可以直接操作函数外部的变量。
练习
- 写一个函数可以判断一个数是不是素数。
#include <math.h>
int isPrime(int num)
{
//1.试除法
//int i = 0;
//for (i = 2;i <num;i++)
//{
// if (num % i == 0)
// {
// return 0;
// }
//}
//return 1;
//2.sqrt
int i = 0;
for (i = 2;i <= sqrt(num);i++)
{
if (num % i == 0)
{
return 0;
}
}
return 1;
}
int main()
{
int i = 0;
for (i = 100; i <= 200; i++)
{
if (isPrime(i))
{
printf("%d\n",i);
}
}
return 0;
}
- 写一个函数判断一年是不是闰年。
int isLeapYear(int year)
{
if ((0 == year % 4) && (year % 100 != 0) || (0 == year % 400))
{
return 1;
}
else
{
return 0;
}
}
int main()
{
int year = 0;
for (year = 1000; year <= 2000; year++)
{
if (isLeapYear(year))
{
printf("%d\n",year);
}
}
return 0;
}
- 写一个函数，实现一个整型有序数组的二分查找。
#include <stdio.h>
int binarySearch(int *arr,int len,int k)
{
int left = 0;
int right = len - 1;
int mid = 0;
while (left <= right)
{
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,8,9,10};
int len = sizeof(arr) / sizeof(arr[0]);
int k = 0;
scanf("%d",&k);
int ret = binarySearch(arr, len, k);
if (ret == -1)
{
printf("没有找到!\n");
}
else
{
printf("找到了，下标为%d\n",ret);
}
return 0;
}
- 写一个函数，每调用一次这个函数，就会将num的值增加1。
#include <stdio.h>
int num = 0;
void fun(int* p)
{
(*p)++;
}
int main()
{
int num =0;
scanf("%d",&num);
fun(&num);
printf("%d\n",num);
fun(&num);
printf("%d\n",num);
fun(&num);
printf("%d\n",num);
return 0;
}
函数的嵌套调用和链式访问
函数和函数之间可以有机的组合的。
函数嵌套调用
在一个函数内部调用另一个函数，叫函数的嵌套调用。函数可以嵌套调用但是不能嵌套定义。
#include <stdio.h>
void print()
{
printf("hehe\n");
}
void print_three_line()
{
int i = 0;
for(i=0; i<3; i++)
{
print();
}
}
int main()
{
print_three_line();
return 0;
}
链式访问
将一个函数的返回值作为另一个函数的实参，叫函数的链式访问。
int main()
{
char arr1[] = "abcdef";
char arr2[] = "xx";
printf("%s\n",strcpy(arr1,arr2));//xx
return 0;
}
#include <stdio.h>
int main()
{
printf("%d", printf("%d", printf("%d", 43)));
return 0;
}
结果是4321。需要了解一下printf函数的返回值。成功时，返回写入的字符总数。如果发生写入错误，返回负数。这里先打印43，然后打印返回值2，最后打印返回值1。
同样地，scanf函数也有返回值：
int main()
{
int n = 0;
int ret = scanf("%d",&n);//输入20
printf("%d",ret);//1
//scanf函数的返回值是成功读取的参数的个数
return 0;
}
成功时，scanf函数的返回值是读取的参数的个数。
如果在读取时发生读取错误或到达文件末尾，返回EOF（-1）。
函数的声明和定义
函数声明：
- 告诉编译器有一个函数叫什么，参数是什么，返回类型是什么。但是这个函数具体是不是存在，无关紧要。
- 函数的声明一般出现在函数的使用之前。要满足先声明后使用。
- 函数的声明一般要放在头文件中的。
函数定义：
函数的定义是指函数的具体实现，交待函数的功能实现。
代码执行从上向下扫描，如果在调用函数之前没有定义或者声明函数，编译时会报错。函数在使用前必须满足先声明再使用。（只声明未定义函数，在链接时报错）
在实际项目中，声明放在头文件中，定义放在源文件中。
分文件：多人协作；模块化，给别人使用，但是又隐藏细节。
举个例子：写一个加法运算
头文件add.h，源文件add.c：
现在想把这个功能提供给别人使用，但是又不想让他人看到函数的具体实现，那么我们可以封装成一个库，VS生成静态库，具体步骤如下，
在项目的属性页：按如下步骤操作
重新生成解决方案后，在项目的Debug文件夹下生成一个add.lib库文件
add.h和add.c封装成一个静态库，使用者只需要有头文件add.h（函数声明）和静态库addl.lib就可以使用add函数，不用关心add函数的具体实现细节。
下面来演示如何使用静态库，我们重新创建一个项目test，
将生成的add.lib和add.h添加到test项目中，然后在test.c中包含头文件test.h，并且导入静态库，然后就可以使用add函数了。
这里解释一下#pragma once的作用：
//作用：防止头文件被重复包含
#pragma once
extern int add(int a,int b);
//如下代码效果相同
#ifndef __ADD_H__
#define __ADD_H__
extern int add(int a,int b);
#endif
函数递归
什么是递归？
程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小。
接收一个整型值（无符号），按照顺序打印它的每一位。 例如： 输入：1234，输出 1 2 3 4。
使用非递归：
void print(int n)
{
int arr[100] = {0};
int i = 0;
while (n)
{
arr[i] = n % 10;
i++;
n /= 10;
}
int j = 0;
for (j = i-1; j >= 0; j--)
{
printf("%d ",arr[j]);
}
}
int main()
{
unsigned int num = 1234;
print(1234);
return 0;
}
使用递归：
//使用递归
//大事化小:
//假设print(1234)函数是打印1234
//拆：print(123) + 打印4
// print(12) + 打印3 + 打印4
// print(1) + 打印2 + 打印3 + 打印4
// printf(1)+printf(2)+printf(3)+printf(4)
void print(unsigned int n)
{
if (n > 9)
{
print(n / 10);
}
printf("%d ", n % 10);
}
int main()
{
unsigned int num = 1234;
print(1234);
return 0;
}
函数调用：从哪里调用的，函数执行结束就回到哪里去。
递归的两个必要条件
1.存在限制条件，当满足这个限制条件的时候，递归便不再继续；
2.每次递归调用之后越来越接近这个限制条件。
递归：递推和回归
1.满足递归条件时，层层递推，从外层向内层不断逼近限制条件；
2.回归：不满足递归条件后，就开始回归，从内层向外层不断回归，函数调用结束返回到外层函数调用的地方。
栈溢出：
关于内存区域分配，简单画个图了解一下，以后会详细学习。
系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归，递归没有结束条件），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出（stack overflow），以上面的练习为例，如果没有递归结束条件if(n > 9)，那么会一直递归下去，print函数不停的调用，开辟空间，却不释放，就会造成栈溢出。
练习
编写函数不允许创建临时变量，求字符串的长度。
#include <string.h>
//代码1 使用临时变量
//int my_strlen(char *p)
//{
// int count = 0;
// while (*p != '\0')
// {
// count++;
// p++;
// }
// return count;
//}
//代码2 临时变量，指针-指针
//int my_strlen(char *p)
//{
// char* s = p;
// while (*p != '\0')
// {
// p++;
// }
// return p - s;
//}
//代码3 递归
int my_strlen(char* p)
{
if (*p != '\0')
{
return 1 + my_strlen(p + 1);
}
return 0;
}
int main()
{
char arr[] = "hello";
//int len = strlen(arr);
//数组名：数组首元素的地址 char*
int len = my_strlen(arr);
printf("%d",len);
return 0;
}
红色部分是从外向内递推部分，层层逼近递归结束条件，绿色部分是递推结束后的回归部分。
递归与迭代
递归：自己调用自己
迭代：类似于循环
对于有些问题，既可以使用递归解决，又可以使用迭代来解决。
例1：求n的阶乘。（不考虑溢出）
#include <stdio.h>
//n的阶乘
//使用递归
int Fac1(int n)
{
if (n <= 1)
{
return 1;
}
else
{
return n * Fac1(n - 1);
}
}
int main()
{
int n = 0;
scanf("%d",&n);
int ret = Fac1(n);
printf("%d",ret);
return 0;
}
例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",ret);
return 0;
}
对于例1和例2，使用递归效率很低。
使用 Fac函数求10000的阶乘（不考虑结果的正确性），程序会崩溃；
在使用 Fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。
为了验证递归效率低，我们改变以下代码：
#include <stdio.h>
int count = 0;//全局变量
int fib(int n)
{
if(n == 3)
count++;
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",ret);
return 0;
}
定义一个全局变量count，当计算第50个斐波那契数时，Fib(3)被计算的次数。最后我们输出看看count，是一个很大很大的值，既然递归效率这么低，那么我们该如何改进呢？
- 将递归改写成非递归。
- 使用static对象替代nonstatic局部对象。在递归函数设计中，可以使用static对象替代nonstatic局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销，而且static对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。
使用循环（非递归）来实现上面两个例子：
#include <stdio.h>
//n的阶乘
//使用循环
int Fac(int n)
{
int i = 0;
int ret = 1;
for (i = 1; i <= n; i++)
{
ret *= i;
}
return ret;
}
#include <stdio.h>
//第n个斐波那契数
//使用循环（迭代）
int Fib1(int n)
{
int a = 1;
int b = 1;
int c = 1;
while(n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
/*if (n <= 2)
{
return 1;
}
else
{
int a = 1;
int b = 1;
int c = 0;
int i = 0;
for (i = 3; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}*/
}
什么时候使用递归？
1.当解决一个问题递归和非递归都可以使用，并且没有明显问题，就可以使用递归；
2.当解决一个问题递归写起来很简单，非递归比较复杂，并且递归没有明显问题，就使用递归；
3.如果使用递归解决问题，写起来简单，但是有明显问题，那就不能使用递归，使用非递归来解决。
提示：
- 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
- 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
- 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。
函数递归的几个经典题目：
- 汉诺塔问题
- 青蛙跳台阶问题