函数

一：函数是什么？

维基百科中对函数的定义：子程序
在计算机科学中，子程序（英语：Subroutine, procedure, function, routine, method, subprogram, callable unit）
（1）：是一个大型程序中的某部分代码， 由一个或多个语句块组成。它负责完成某项特定任务，而且相较于其他代码，具备相对的独立性。
（2）：一般会有输入参数并有返回值，提供对过程的封装和细节的隐藏。这些代码通常被集成为软件库。

二：C语言中函数的分类

（1）库函数：C语言内部提供的函数。
（2）自定义函数：自我发挥写出的函数。

1：库函数

（1）：库函数存在的意义：

1. 我们知道在我们学习C语言编程的时候，总是在一个代码编写完成之后迫不及待的想知道结果，想把这个结果打印到我们的屏幕上看看。这个时候我们会频繁的使用一个功能：
2. 将信息按照一定的格式打印到屏幕上（printf）。
3. 在编程的过程中我们会频繁的做一些字符串的拷贝工作（strcpy）。
4. 在编程是我们也计算，总是会计算n的k次方这样的运算（pow）。**
5. 为了提高我们的工作的效率,防止bug的出现,我们就引入了库函数

（2）：库函数的学习与使用

像上面我们描述的基础功能，它们不是业务性的代码。我们在开发的过程中每个程序员都可能用的到，为了支持可移植性和提高程序的效率，所以C语言的基础库中提供了一系列类似的库函数，方便程序员进行软件开发。

库函数的使用不需要专门去记，我们可以通过查找了解它们的使用方式。

这里推荐一个网站和一个应用程序

（1）www.cplusplus.com
（2）MSDN(Microsoft Developer Network)
（3）http://en.cppreference.com（英文版）
（4）http://zh.cppreference.com（中文版）
通过这些方式，我们可以查找到它们的信息，例如：函数名、形式参数、需要的头文件和返回值等必要的信息。

这些工具的语言都是英文，在学习编程的工程中我们需要学习英文，
下面来举两个库函数的例子

strcpy

char * strcpy ( char * destination, const char * source );
1

上面英文简单说明了目的地是返回值
加深的理解就是：
strcpy函数会把源头source的数据拷贝到目的地空间里面以后，会把目的地空间的起始地址给返回回来。

//strcpy的用法
#include
#include
int main()
{
	char arr1[20] = { "xxxxxxxxxxxxxxx" };
	char arr2[]   = { "hello bit" };
	strcpy(arr1, arr2);//arr1为目的地,arr2为源头,为了将arr2数组里面的内容拷贝到arr1里面
	printf("%s\n", arr1);
	return 0;
//arr1与t对齐的后面的x,也就是数组下标为9的x,被改成\0拷贝了过来
//实际上打印的结果为hello bit(\0不显示但存在)
}
1
2
3
4
5
6
7
8
9
10
11
12
13

memset(内存设置函数)

void * memset ( void * ptr, int value, size_t num );
1

补充:该值指的是num的字节数

//memset的用法
#include
#include
int main()
{
	char arr[] = { "hello bit" };
	memset(arr, 'x', 5);
	printf("%s\n", arr);
	return 0;
}
//memset中间一定是unsigned char类型,5则表示arr数组里面前五个东西被x所取代
1
2
3
4
5
6
7
8
9
10
11

注：
但是库函数必须知道的一个秘密就是：使用库函数，必须包含 #include 对应的头文件。
这里对照文档来学习上面几个库函数，目的是掌握库函数的使用方法。

2：自定义函数

（1）：自定义函数的组成

自定义函数由程序员自主设计，和普通的函数一样有函数名、返回类型、形式参数等。

基本结构如下：

ret_type fun_name(para1, * )
{
    statement;//语句项
}
//ret_type 返回类型
//fun_name 函数名
//para1    函数参数
1
2
3
4
5
6
7

（2）：例题

例题一：写一个函数找出两个整数的最大值

//写一个函数找出两个整数的最大值
#include
int get_max(int x, int y)
{
    if (x > y)
    {
        return x;
    }
    else
    {
        return y;
    }
    //简便的代码,一行代替上面函数体里面的代码
    //return(x > y ? x : y);
}
//从之前笔记一:函数是什么里面的定义得知-
//上述函数就是一个语句块,它负责完成某项特定的任务—求两个数的最大值

int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    int c = get_max(a, b);
    printf("%d\n", c);
    return 0;
}
//输入:10 20
//输出:20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

例题二：写一个函数交换两个整型变量的内容

//写一个函数交换两个整型变量的内容

//错误示范
#include
void swap(int a, int b)
{
    int temp = 0;
    temp = a;
    a = b;
    b = temp;
}
int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    printf("交换前：a=%d，b=%d\n", a, b);
    swap(a, b);
    printf("交换前：a=%d，b=%d\n", a, b);
    return 0;
}
//输入：10 20
//输出：
//交换前：a=10，b=20
//交换后：a=10，b=20
//没有达到相应的效果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

正确的代码：

//正确代码
#include
void swap(int* pa, int* pb)
{
    int temp = 0;
    temp = *pa;
    *pa = *pb;
    *pb = temp;
}
int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    printf("交换前：a=%d，b=%d\n", a, b);
    swap(&a, &b);
    printf("交换前：a=%d，b=%d\n", a, b);
    return 0;
}
//输入：10 20
//输出：
//交换前：a=10，b=20
//交换后：a=20，b=10
//
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

错误的原因我们可以直接到传址应用 那一页会解释清楚

三：函数中的参数

1：实际参数(实参)

真实传给函数的参数，叫实参。
实参可以是：常量、变量、表达式、函数等。
在调用函数时，它们都必须有确定的值，以便把这些值传送给形参。
例如上述代码的get_max(a,b)，a b就是实际参数，他们会分别传到函数里面的形式参数x y里面

2：形式参数(形参)

形式参数是指函数名后括号中的变量。
形式参数只有在函数被调用的过程中才实例化（分配内存单元），所以叫形式参数。因此形式参数只在函数中才有效。

切记下面这句话非常重要！！！！！
当函数调用的时候,实参传给形参，形参将是实参的一份临时拷贝，所以对形参的修改，不影响实参。
形参将是实参的一份临时拷贝这几个字要牢记下来！！！

四：函数的调用

1：传值调用

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

所以，我们在不改变函数实参的时候可以使用传值调用。

下面来举个例子
写一个程序计算两个整数的和：

#include
int add(int x, int y)
{
    return x + y;
}
int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    int c = add(a, b);
    printf("%d\n", c);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在这个程序中，a和b是实际参数，我们只是使用a和b进行操作，而没有改变a和b的数值等属性，这时我们就可以使用传值调用，再将操作得到的值返回。

2：传址调用

传址调用是把函数外部创建变量的内存地址传递给函数参数的一种调用函数的方式。
这种传参方式可以让函数和函数外边的变量建立起真正的联系，也就是函数内部可以直接操作函数外部的变量。

我们用上面交换两个数的代码来举例子：

#include
void swap(int* pa, int* pb)
{
    int temp = 0;
    temp = *pa;
    *pa = *pb;
    *pb = temp;
}
int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    printf("交换前：a=%d，b=%d\n", a, b);
    swap(&a, &b);
    printf("交换前：a=%d，b=%d\n", a, b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在这个程序中，我们改变了a和b的数值，这时我们就需要使用传址调用，因为在传值调用中形参的改变是不会影响实参的。

接下来我们就知道为啥哪里错了
下面我们来详细解读一下Swap函数这两个代码

//错误代码
#include
void swap(int a, int b)//返回类型为void表示不返回，此处的int a与int b表示形式参数和它们的类型
{
    int temp = 0;//定义一个临时变量
    temp = a;//把a的值赋给temp
    a = b;//把b的值赋给a
    b = temp;//把temp的值赋给b，完成交换操作
    //注意，因为形参只是实参的一份临时拷贝，在整个函数中我们改变的只是实参，出函数后形参被销毁无法改变实参
}
int main()
{
    int a = 0;//创建变量a
    int b = 0;//创建变量b
    scanf("%d %d", &a, &b);//输入数值
    printf("交换前：a=%d，b=%d\n", a, b);//展示
    swap(a, b);//交换函数，将a，b传进去
    printf("交换前：a=%d，b=%d\n", a, b);//实参依旧是a和b的原始值，没有达到我们的目的
    return 0;
}

//正确代码
#include
void swap(int* pa, int* pb)//void表示不返回，此处的int* pa与int* pb表示形式参数和它们的类型
{
    int temp = 0;//定义临时变量
    temp = *pa;//用地址找到实参a并赋给temp
    *pa = *pb;
    //把用地址找到的实参b赋给用地址找到的实参a
    *pb = temp;//用地址找到实参b并赋给temp
    //跳出函数时，被销毁的形参只是两个指针变量，此时实参的交换已经完成
}
int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    printf("交换前：a=%d，b=%d\n", a, b);
    swap(&a, &b);//传入地址
    printf("交换前：a=%d，b=%d\n", a, b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

3：练习

（1）：写一个函数可以判断一个数是不是素数。

//写一个函数可以判断一个数是不是素数。
#include
#include
int is_primer(int n)
{
	int j = 0;
	for (j = 2; j <= sqrt(n); j++)
	{
		if (n % j == 0)
		{
			return 0;
			//如果经过return 0,
			//则下一步往函数int is_primer(int n)的大括号走,
			//然后进入主函数is_primer(i)那里进行判断i是否等于1	
		}
	}
	//j没有任何一个数能整除n,说明它一定是素数,则返回1,否则返回0
	return 1;
}
int main()
{
	//打印100~200之间的素数
	int i = 0;
	for (i = 100; i <= 200; i++)
	{
		//判断i是否为素数
		if (is_primer(i) == 1)//如果是素数返回的结果是1,则令函数==1,将素数打印出来
		{
			printf("%d ", i);
		}
		//如果这个函数返回值不等于1
		//则继续进入主函数的for循环,然后for循环再进入if中判断,
		//判断完后,将i传到形式参数里面去
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

注意：如果函数不写返回值，函数会默认返回一个值，有些编译器上返回的是：最后一条指令产生的结果

（2）：写一个函数判断一年是不是闰年。

//写一个函数判断一年是不是闰年。
int is_leap_year(int year)
{
	if (((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0))
		return 1;
	else
		return 0;
}
//有一种更简单的方法,不需要用if...else
//int is_leap_year(int year)
//{
//	return ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0);
//}
int main()
{
	int y = 0;
	int count = 0;
	for (y = 1000; y <= 2000; y++)
	{
		//判断y是不是闰年
		if (is_leap_year(y) == 1)
		{
			count++;
			printf("%d ", y);
		}
	}
	printf("\ncount = %d\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

（3）：写一个函数，实现一个整形有序数组的二分查找。

//写一个函数，实现一个整形有序数组的二分查找
//错误代码
#include
//int binary_search(int* arr, int a)//地址传过去,得要指针接收,所以本质还是一个指针
int binary_search(int arr[], int a)
{
	int left = 0;
	int right = sizeof(arr)/sizeof(arr[0]) - 1;//right一直是0
	//上面的那一行代码是有逻辑错误的,
	//因为数组传参，传递的是数组首元素的地址
	//所以sizeof(arr)=1,所以1-1=0

	int mid = 0;
	while (left <= right)
	{
		mid = left + (right - left) / 2;//找中间的元素,防止越界
		if (arr[mid] > a)//中间元素大于查找值，就从右缩小一半的范围
		{
			right = mid - 1;//可以使用--mid，但不推荐
		}
		else if (arr[mid] < a)//中间元素小于查找值，就从左缩小一半的范围
		{
			left = mid + 1;//可以使用++mid，但不推荐
		}
		else
		{
			return mid;//找到了，返回下标
		}
	}
	if (left > right) //正常情况下不会出现
	{
		return -1;//找不到，返回-1
	}
}
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 0;
	scanf("%d", &k);
	//找到了返回下标，0~9
	//找不到返回 -1(这里不能返回0,因为数组的第一个数字下标是0,如果return 0很有可能会对结果造成影响)
	//传数组,一个元素4个字节,数组中10个元素40个字节,
	//把40个字节全都移过去,如果int arr[]为了接收也创建了一个40字节的空间
	//这样空间会有大量的浪费,所以c语言有了以下规定:
	//数组传参，传递的是数组首元素的地址
	int ret = binary_search(arr, k);
	if (-1 == ret)
		printf("找不到\n");
	else
		printf("找到了，下标是:%d\n", ret);

	return 0;
}
//正确代码(在主函数里面定义一个sz变量)
#include
//地址传过去, 得要指针接收, 所以本质还是一个指针
//int binary_search(int* arr, int a, int sz)//数组传参，传递的是数组首元素的地址
int binary_search(int arr[], int a, int sz)//形参为数组、需要查找的整数、数组的元素个数
{
	int left = 0;
	int right = sz - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = left + (right - left) / 2;//找中间的元素,防止越界
		if (arr[mid] > a)//中间元素大于查找值，就从右缩小一半的范围
		{
			right = mid - 1;//可以使用--mid，但不推荐
		}
		else if (arr[mid] < a)//中间元素小于查找值，就从左缩小一半的范围
		{
			left = mid + 1;//可以使用++mid，但不推荐
		}
		else
		{
			return mid;//找到了，返回下标
		}
	}
	if (left > right) //正常情况下不会出现
	{
		return -1;//找不到，返回-1
	}
}
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//只能在主函数里面定义sz变量,sizeof(arr)在主函数里使用不需要传递地址
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 0;
	scanf("%d", &k);
	//找到了返回下标，0~9
	//找不到返回 -1(这里不能返回0,因为数组的第一个数字下标是0,如果return 0很有可能会对结果造成影响)
	//数组传参，传递的是数组首元素的地址
	int ret = binary_search(arr, k, sz);//再多加一个sz变量,传到形参上去
	if (-1 == ret)
		printf("找不到\n");
	else
		printf("找到了，下标是:%d\n", ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

（4）：写一个函数，每调用一次这个函数，就会将 num 的值增加1

#include
void Add(int* p)//在主程序内定义一个变量储存调用的次数，因为需要改变变量的值，所以进行传址调用
{
    printf("hehe\n");
    (*p)++;//解引用找到变量再加1，注意这个括号不能忘
    //否则，*p++就表示每次这个指针先向后移动4个字节，然后解引用
}
int main()
{
	int num = 0;
	Add(&num);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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

1.嵌套调用

函数可以根据需要进行相互调用。
举两个例子

#include
int main()
{
    printf("Hello world\n");
    return 0;
}
//这是每一个初学者都会写的代码,我们先调用了main函数，
//然后在main函数的内部又调用了printf函数,这就是嵌套调用.(可以理解为复合函数)
1
2
3
4
5
6
7
8

#include 
void new_line()
{
    printf("hehe\n");
}
void three_line()
{
    int i = 0;
    for (i = 0; i < 3; i++)
    {
        new_line();
    }
}
int main()
{
    three_line();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意：函数可以嵌套调用，但是不能嵌套定义。

2.链式访问

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

#include
#include
int main()
{
	int len = strlen("abcdef");
	printf("%d\n", len);
	//可以利用链式访问简化代码,如下:
	printf("%d\n", strlen("abcdef"));
	return 0;
}
1
2
3
4
5
6
7
8
9
10

strlen函数的返回值变成了printf函数的参数，这就把这两个函数像锁链一样串联起来，也就是链式访问。

（1）：链式访问的经典例题

请问下面的程序输出是？

#include
int main()
{
    printf("%d", printf("%d", printf("%d", 43)));
    return 0;
}
1
2
3
4
5
6

答案：4321

重要知识点：printf这个函数的返回值是它打印字符的个数，

首先进入最外层的printf函数

这层函数需要第二层函数 printf(“%d”, printf(“%d”, 43)) 的返回值

而第二层的printf函数又需要第三层函数 printf(“%d”, 43) 的返回值

先执行第三层函数，在执行完第三层的 printf(“%d”, 43) 函数后，返回打印字符的个数为2

于是变成了这样printf(“%d”, printf(“%d”, 2))

第二层得到返回值2，打印2，而此时第二层函数也返回它打出的字符的个数1

于是变成了这样printf(“%d”, 1) ，最后打印1，

也就形成了4321的输出结果

六：函数的声明和定义

1：函数的声明

1.告诉编译器有一个函数叫什么，参数是什么，返回类型是什么。但是具体是不是存在，函数
声明决定不了。
2.函数的声明一般出现在函数的使用之前。要满足先声明后使用。
3.函数的声明一般要放在头文件中的。

2：函数的定义

1.函数的定义是指函数的具体实现，交待函数的功能实现。相当于我们平常创建自定义函数的步骤。

2.函数不能嵌套定义

3：程序的分块化编写

我们在写代码的时候可能会想：我把所有的代码写在一个源文件中，这样找起来不就方便了吗。

其实，这样的习惯对日后程序的开发是不利的。

我们的社会是有各自的分工的，当我们在开发一个程序的时候，我们往往只需要负责一个大的工程中的部分内容，比如一个人去写主程序，一个人写函数等等，而我们将工程的各个部分分开就可以更快地快找到bug并对应修复。

这样，当我们写一个函数时，就需要这样的文件分配：

函数的声明，类型的定义，头文件的包含——头文件.h
函数定义——函数实现的源文件.c
每一个函数都可以分成这两个文件编写，也可以几个函数写在两个文件中。

比如我们写一个两个数之和的工程,有诸多程序员分工完成
甲创立了头文件 add.h

#pragma once
//头文件中放:函数的声明,类型的定义,头文件的包含
int Add(int x,int y)
1
2
3

乙创立的小源文件add.c

int Add(int x,int y)
{
	return x + y;
}
1
2
3
4

test.c里面

#include "add.h"//引用头文件
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a. & b);
	int c = Add(a, b);
	printf("%d\n", c);
	return 0;
}
1
2
3
4
5
6
7
8
9
10

我们分模块来写代码的好处是可以把一些实现文件的必要代码给隐藏起来
比如有个程序猿叫张三
他业余时间写了一个游戏引擎，有个公司想买他的游戏引擎
张三同意卖给他，但不希望给他看到源码，那他到底应该怎么做
他是这样做的：
张三写了这两个代码
假设他在VS环境下工作,点击 头文件，添加现有项，将上面两个代码文件添加过来
这个游戏引擎恰好是李四想把它买过来的一个项目
张三心想：我可以让你用，但我不想让你看到具体怎么实现的
于是他点击

点击应用
使用完后add.c里面的代码运行不起来

这个add.lib文件就是张三写的游戏引擎的静态库
李四买下来后打开来看add.lib文件,是一堆乱码,
张三于是给他了一个使用说明书
首先把lib文件放到这里来

test.c的代码最终应该这样显示

#include "add.h"//引用头文件
#pragma comment(lib, "add.lib")//加载引用静态库
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a. & b);
	int c = Add(a, b);
	printf("%d\n", c);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

七：函数的递归

1：什么是递归

程序调用自身的编程技巧称为递归(recursion).(递归也就是程序自己调用自己)
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的
一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
递归策略
只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的主要思考方式在于：把大事化小

下面介绍一个最简单的递归

#include
int main()
{
	printf("hehe\n");
	main();
	return 0;
}
//死递归hehe,到最后程序因为栈溢出而自动跳出(挂掉了)
1
2
3
4
5
6
7
8

那什么时候会发生栈溢出(Stack overflow)呢？
每一次函数的调用都会在栈区申请内存空间，而上面代码递归无限次申请，最终导致栈溢出.

2：递归的两个必要条件

存在限制条件，当满足这个限制条件的时候，递归便不再继续。

每次递归调用之后越来越接近这个限制条件。

（1）：练习1：（画图讲解）

接受一个整型值（无符号），按照顺序打印它的每一位

例如：输入：1234，输出 ：1 2 3 4

#include
void print(unsigned int n)
{
	if (n > 9)//如果n是两位数的话
	{
		print(n / 10);//满足递归的两个必要条件
	}
	printf("%d", n % 10);
	
}
int main()
{
	unsigned int num = 0;
	//无符号整型用%u
	scanf("%u", &num);//1234
	print(num);//按照顺序打印num的每一位
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

下面我们来分析递归的过程

//递归的思考方式：大事化小
//
//print(1234)
//print(123) 4   
//print(12) 3 4
//print(1) 2 3 4
//1 2 3 4
//
print(1234);//这个函数从上到下，先递进后回归
//1234大于9，进入if语句,第一层
print(1234)
{
    if (n > 9)//n=1234,满足条件，进入if
    {
        print(123);
    }
    printf("%d ", n % 10);//第一层，n%10=4
}
//print(123)展开，n=123满足条件，继续进入下一层,接着递归
print(123)
{
    if (n > 9)//n/10=123,满足条件，进入if
    {
        print(12);
    }
    printf("%d ", n % 10);//第二层，n%10=3
}
//print(12)展开，n/10=1此时不满足条件，不会继续进入下一层的if语句
print(12)
{
    if (n > 9)//n=12,不满足条件，不进入if
    {
        print(1);
    }
    printf("%d ", n % 10);//第三层，n%10=2
}
print(1)
{
    if (n > 9)//n=1,不满足条件，不进入if
    {
        print(0);
    }
    printf("%d ", n % 10);//第三层，n%10=1
}
//递归的“递”此时已经完成，我们将这个代码整理一下，查看它时如何“归”的
print(1234)
{
    {
        {
            {
                printf("%d ", n % 10);//第四层，n%10=1
            }
            printf("%d ", n % 10);//第三层，n%10=2
        }
        printf("%d ", n % 10);//第二层，n%10=3
    }
    printf("%d ", n % 10);//第一层，n%10=4
}
//代码从第四层开始向外执行，故可以实现数字的按位打印
//输出：1 2 3 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

下面补充一点函数栈帧的知识点(修炼内功)(博主摸鱼王胖嘟嘟的文章写的详细且易懂，可以收藏一下)

函数的栈帧与销毁

这里我就简单讲一下
之前提过寄存器的种类，我们现在再来回忆一下

ebp与edp是用来维护函数栈帧的

那函数具体怎么调用的呢？首先我们在VS里面按下F10，再点击反汇编，这个时候我们就能看到汇编代码。我们取消“显示符号名”，因为我们要观察内存地址的具体布局

提示：
1.dword是四个字节
2.每一次初始化4个字节，总共初始化ecx次，最终初始化成eax,0CCCCCCCCh的内容
3.push：压栈：给栈顶放一个元素
pop：出栈：从栈顶删除一个元素

从中我们可以发现，实际上我们根本没有定义形参
我们通过mov,push指令进行传参（把b、c进行形参压栈压到[ebp+8],[ebp+0Ch(12)]中来）
Add(a,b)是先传右边再传左边的。
a’与b’（x与y）实际上就是a,b实参的临时拷贝

return z之后函数便开始销毁，下面我们可以看一下反汇编的代码

00C213F1 5F   		pop   edi
00C213F2 5E   		pop   esi
00C213F2 5B   		pop   ebx
//pop三次 相当于之前连续push三次的逆过程,连续在栈顶弹出值分别存放到edi,esi,ebx中
//pop完后,这些空间没必要存在了,应该被销毁
00C213F4 8B E5 		mov	  esp,ebp
//mov将ebp赋给了esp,这个时候esp与ebp在同一个位置上

00C213F6 5D			pop   ebp
//把ebp pop出来之后ebp回到main函数的栈底,esp回到main函数的栈顶	
1
2
3
4
5
6
7
8
9
10

如图所示esp返回到main函数的栈顶了

00C213F7 C3 		ret
//ret指令的执行,跳到栈顶弹出的值就是call指令的下一条指令的地址
//此时esp+4(pop了一下),栈顶的地址也弹出去了,esp指向了00C21450(call)的底部		
1
2
3

调用完Add函数，回到main函数的时候，继续往下执行

00C21450 83 C4 08		add			esp,8
//回到call指令的下一条地址,esp直接+8,把x,y形参的空间释放,esp这个时候指向edi的顶端
00C21453 89 45 E0		mov			dword ptr [ebp-20h],eax
//把eax中的值,存放到[ebp-20h(也就是c)]里面去
//函数的返回值是由eax寄存器带回来的
1
2
3
4
5

解读完后我们就可以解答以下几个问题

• 局部变量是怎么创建的？
  答：首先为函数分配好栈帧空间，空间里面初始化好一部分，然后给局部变量的栈帧空间里面分配一点空间。
• 为什么局部变量的值不初始化的时候是随机值？
  答：不初始化的话由于局部变量来自于main函数的栈帧，这里面的值是随机放进去的，初始化后就可以覆盖随机值了。
• 函数是怎么传参的？传参的顺序是怎么样的？
• 形参和实参的关系是什么样的？
  答：形参是实参的一份临时拷贝。
• 函数的调用时怎么做的？
  （3、5）答：当要去调用函数的时候，没调用之前就已经push，把(a,b)这两个参数从右向左开始压栈。当我们进入形参函数的时候，其实在Add函数的栈帧里面，通过指针的偏移量，找回了函数的形参。
• 函数调用结束后是怎么返回的？
  答：在调用之前我们就把call指令的下一条指令的地址给存放进去了，把ebp调用这个函数的上一个函数栈帧的ebp给存进去了，当函数调用完需要返回的时候，弹出ebp，就能找到上一个函数调用的ebp，指针往下(高地址)走的时候，就能走到esp的顶部，从而能够回到main函数的栈帧空间，之后，我们记住了call指令的下一条指令的地址，当我们返回的时候，我们就可以跳转到call指令的下一条指令的地址，让函数调用后可以返回，返回值通过eax寄存器方式带回来。

（2）：练习2：（画图讲解）

求字符串长度，下面介绍三种方法：
方法一：

//方法一
#include
#include
int main()
{
	char arr[] = { "abc" };
	int len = strlen(arr);
	printf("%d", arr);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11

方法二：利用函数与循环

//方法二
#include
int my_strlen(char* str)
{
	int count = 0;
	while (*str != '\0')
	{
		count++;
		str++;
	}
	return count;
}
int main()
{
	char arr[] = { "abc" };
	int len = my_strlen(arr);
	printf("%d", len);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法三：递归(简便，不需要创建临时变量)

//strlen("abc");
//1+strlen("bc");
//1+1+strlen("c");
//1+1+1+strlen("");
//1+1+1+0=3
#include
int my_strlen(char* str)
{
	if (*str != '\0')
	{
//如果第一个字符不是"\0",则字符串至少包含一个字符
//可以剥出来个1,str+1是下一个字符所指向的地址
//空字符第一个是"\0"
		return 1 + my_strlen(str + 1);
//注意:这里str++并不能代替str+1的作用
//我们把str+1之后的地址传下去了,而留下来str还是原来的str.
//因为str++是先使用再++,
//那么根据原理传进去的str还是原来的str(原来是a的地址,传进去还是a的地址)
//所以按照原理:++str能代替str+1的作用,但并不推荐这样做,
//因为如果递归回来之后使用str的话,留下来的str不是原来的str了.
	}
	else
		return 0;
}
int main()
{
	char arr[] = { "abc" };
	int len = my_strlen(arr);
	printf("%d", len);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

方法三看上去代码很少，但实际上程序内部重复了大量的计算.

3：函数的递归与迭代

（1）：什么是迭代

迭代实际上就是重复，循环是一种特殊的迭代。

（2）：优缺点

函数递归中我们一层一层调用函数，它的优点是所需代码量少，简洁。但缺点主要有两个，一方面，大量重复的计算拖慢了程序的运行速度；另一方面，函数每一次被调用的时候都需要在栈区开辟相应的空间，当递归过深时可能会出现栈溢出。（栈区的空间已经被用完了，程序无法继续进行了）

当我们使用迭代时，循环不需要大量调用函数，重复的计算会少很多，这个程序的运行速度会加快不少，只是这个程序的代码量会大很多。

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

//斐波那契数列
//1 1 2 3 5 8 13 21 34 55 ....
//方法一:递归法
//		 n<=2 1
//Fib1(n) 
//		 n>2 Fib1(n-1)+Fib1(n-2);//第三个数加第二个数
#include
int Fib1(int n)
{
	//如果想知道某个斐波那契数究竟计算了多少次,可以设置一个全局变量count
	//if (n == k)//算第k个斐波那契数被计算了多少次
		//count++;
	if (n <= 2)
		return 1;
	else
		return Fib1(n - 1) + Fib1(n - 2);
}
//int count = 0;
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret1 = Fib1(n);//定义一个ret来接受上面函数的返回值
	printf("%d", ret1);
	//printf("count=%d\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

求n的阶乘

//求n的阶乘
//方法一:递归法
//1*2*3=Fac(3)
//1*2*3*4=Fac(3)*4
// 
//		 n<=1  1			
//Fac(n)
//		 n>1 n*Fac(n-1);

#include
int Fac1(int n)
{
	if (n <= 1)
		return 1;
	else
		return n * Fac1(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret1 = Fac1(n);//定义一个ret来接受上面函数的返回值
	printf("%d", ret1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

上面两个代码看似很简便，但实际运行的时候却发现了大问题：

在使用 Fib1 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。

使用 Fac1函数求10000的阶乘（不考虑结果的正确性），程序会崩溃

为什么呢？
在使用Fib函数的时候，当n=50的时候，光n=46就被计算(出现)了3次，这样会使得程序运行速度非常慢。
在使用Fac1函数的时候，当求10000的阶乘的时候，会出现 stack overflow（栈溢出）的信息，系统分配给程序的栈空间是有限的，但是如果出现了死循环,或者(死递归),这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

那么我们怎么纠正这个问题呢？
把递归改成非递归
改正后的代码如下

//斐波那契数列
//1 1 2 3 5 8 13 21 34 55 ....
//方法二:迭代  
#include
int Fib2(int n)
{
	int a = 1;//
	int b = 1;//前两个数都是1
	int c = 1;//对斐波那契数列中前两个数之和的第三个数初始化
	//不能令c=0,如果输入的n小于2,那直接return 0了,很显然不行
	while (n > 2)//第三个斐波那契数的时候开始循环
	{
	//1 1 2 3 5 8 13 21 34 55 ....
	//
	//  
	//      a b c.....(斐波那契数前两个数之加赋给第三个数,以此类推...)
	//		  a b c....
	//			a b c....	  
		c = a + b; //斐波那契数前两个数之加赋给第三个数
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret2 = Fac2(n);//定义一个ret来接受上面函数的返回值
	printf("%d", ret2);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//求n的阶乘
//方法二:迭代法
int Fac2(int n)
{
	int i = 0;
	int ret2 = 1;//阶乘初始化必然为1
	for (i = 1; i <= n; i++)
	{
		ret2 = ret2 * i;
	}
	return ret2;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret2 = Fac2(n);//定义一个ret来接受上面函数的返回值
	printf("%d", ret2);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

提示：

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

4：函数递归经典问题

（1）：汉诺塔问题

一．起源：
　　汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

二．抽象为数学问题：
　　如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

（1）n == 1

第1次 1号盘 A---->C sum = 1 次

(2) n == 2

第1次 1号盘 A---->B
第2次 2号盘 A---->C
第3次 1号盘 B---->C sum = 3 次

（3）n == 3

第1次 1号盘 A---->C
第2次 2号盘 A---->B
第3次 1号盘 C---->B
第4次 3号盘 A---->C
第5次 1号盘 B---->A
第6次 2号盘 B---->C
第7次 1号盘 A---->C sum = 7 次

不难发现规律：1个圆盘的次数 2的1次方减1

2个圆盘的次数 2的2次方减1
3个圆盘的次数 2的3次方减1
。 。 。 。 。
n个圆盘的次数 2的n次方减1

故：移动次数为：2^n - 1

算法分析

（步骤1）　　如果是一个盘子

直接将a柱子上的盘子从a移动到c

否则

（步骤2）　　　　 先将a柱子上的n-1个盘子借助c移动到b（图1），

肯定没有c柱子是不能移动的，已知函数形参是hanoi(int n,char a,char b,char c)。

代表将a柱子上的盘子借助c柱子移动到b柱子，这里调用函数的时候是将a柱子上的n-1个

盘子借助c柱子，移动到b柱子。所以这里需要将位置调换一下hanoi(n-1,a,c,b)。

（步骤3）　　　　此时移动完如图1，但是还没有移动结束，首先要将a柱子上的最后一个盘子（第n个）盘子直接移动到c（图2）

（步骤4）　　　　最后将b柱子上的n-1个盘子借助a移动到c（图3）

// 汉诺塔
#include
void hanoi(int n, char a, char b, char c)//这里代表将a柱子上的盘子借助b柱子移动到c柱子
{
	if (1 == n)//如果是一个盘子直接将a柱子上的盘子移动到c
	{
		printf("%c-->%c\n", a, c);
	}
	else
	{
		hanoi(n - 1, a, c, b);//将a柱子上n-1个盘子借助c柱子，移动到b柱子
		printf("%c-->%c\n", a, c);//再直接将a柱子上的最后一个盘子移动到c
		hanoi(n - 1, b, a, c);//然后将b柱子上的n-1个盘子借助a移动到c
	}
}
int main()
{
	int n = 0;
	printf("请输入需要移动的圆盘个数:");
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');//移动A上的所有圆盘到C上
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（2）：青蛙跳台阶问题

（1）问题描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

任务：青蛙跳上一个 n 级的台阶总共有多少种跳法。

规定：青蛙一次可以跳一个或两个台阶。

（2）问题分析
当n = 1时， 有1种跳法；
当n = 2时，青蛙跳一级再跳一级；青蛙直接跳上两级。有2种跳法；
当n = 3时，青蛙跳一级三次；青蛙跳一级再跳两级；青蛙跳两级再跳一级，有3种跳法；
当n = 4时，有5种跳法；
当n = 5时，有8种跳法；…

规律类似于Fibonacci数列

（3）递归结束的判断

比如说，青蛙需要跳上五级台阶。

为了找到五级台阶的种数，我们需要找到四级台阶和三级台阶的数值。

为了找到四级台阶的种数，我们需要找到三级台阶和二级台阶的数值，此时其中一个数值不需要递归了。

为了找到三级台阶的种数，我们需要找到二级台阶和一级台阶的数值，此时另一个数值也不需要递归了。

此时，我们的递归此时就可以中断了，所以我们得到递归终止的判断依据：柱1上的圆盘数小于等于一时，跳出递归。

//青蛙跳台问题
#include
//或者运用void函数,但之前要定义一个全局变量count
//int count = 0;//创建全局变量来统计个跳法个数
//void frog_jump(int n)
//{
//	if (n == 0)//当台阶数为0是跳法个数加1
//		count++;
//	else if (n < 0);
//	else
//	{
//		frog(n - 1);
//		frog(n - 2);
//	}
int frog_jump(int n)
{
	//int sum = 0;
	if (1 == n)//等于1时，sum=1
	{
		return 1; //sum += 1
	}
	else if (2 == n)//等于2时，sum=2
	{
		return 2;//sum += 2;
	}
	else//大于3时，开始递归
	{
		return frog_jump(n - 1) + frog_jump(n - 2);//sum = frog_jump(m - 1) + frog_jump(m - 2);
	}
	//return sum;
}
int main()
{
	int n = 0;
	printf("请输入台阶的个数:");
	scanf("%d", &n);
	int ret = frog_jump(n);
	printf("一共有%d种跳法\n", ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

（3）：青蛙跳台阶问题(进阶版)

题目(1)： 从前有一只青蛙想跳台阶去等峰，若该青蛙一次可以跳上1级台阶、也可以跳上2级……（n-1）级、n级。那么该青蛙跳上第n级的台阶时总共有多少种跳法。（前提是n个台阶会有一次n阶的跳法）

（1）解题思路：

若n为1级台阶：f(1) = 1 (只可能有一种跳法)
若n为2级台阶：f(2) = f(2 - 1) + f(2 - 2)（会有两个跳台阶的方法，一次1阶或者一次2阶）
若n为3级台阶：f(3) = f(3 - 1) + f(3 - 2) + f(3 - 3)（会有三种跳台阶的方法，一次1阶、2阶、3阶）
……
……
若n为(n - 1)级台阶：

f(n-1) = f((n-1)-1) + f((n-1)-2) + … + f((n-1)-(n-2)) + f((n-1)-(n-1))
f(n-1) = f(0) + f(1)+f(2)+f(3) + … + f((n-1)-1)
f(n-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2)

若n为n级台阶：

f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)
f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) + f(n-1)

结合f(n-1)和f(n)的情况你会发现f(n) = f(n-1) + f(n-1)，所以可得： f(n) = 2*f(n-1)。

#include
int frog_jump_step(int n)
{
	if (n <= 1)
	{
		return 1;
	}
	else
		return 2 * frog_jump_step(n - 1);
}
int main()
{
	int n = 0;
	printf("请输入青蛙应该跳的台阶个数:");
	scanf("%d", &n);
	int sum = frog_jump_step(n);
	printf("一共有种%d种跳法\n", sum);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

题目(2)：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个m级的台阶总共有多少种跳法？

（1）解题思路
与上面不太一样的情况就是最后青蛙跳的台阶不是n级，所以可能会出现跳过了的现象。
先列多项式：
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-m)
f(n-1) = f(n-2) + f(n-3) + … + f(n-m) + f(n-m-1)
化简得：f(n) = 2f(n-1) - f(n-m-1)

#include
int frog_jump_step(int n,int m)
{
	if (n > m)
	{
		return 2 * frog_jump_step(n - 1, m) - frog_jump_step(n - 1 - m, m);
	}
	else
	{
		if (n <= 1)
		{
			return 1;
		}
		else
			return 2 * frog_jump_step(n - 1);
	}	
}
int main()
{
	int n = 0;
	int m = 0;
	printf("请输入青蛙应该跳的台阶个数:");
	scanf("%d", &n);
	int sum = frog_jump_step(n, m);
	printf("一共有种%d种跳法\n", sum);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27