简单点_c_lesson10(递归)

1.递归

1.什么是递归？
程序调用自身的编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，
它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 
递归的主要思考方式在于：把大事化小
2.递归的两个必要条件
(1)存在限制条件，当满足这个限制条件的时候，递归便不再继续。
(2)每次递归调用之后越来越接近这个限制条件。
3.例子
（1）：接收一个整型值（无符号），按照顺序打印它的每一位。 例如： 输入：1234，输出 1 2 3 4.
（2）：编写函数不允许创建临时变量，求字符串的长度。
（3）：求n的阶乘。（不考虑溢出）
（4）：求第n个斐波那契数。（不考虑溢出）
（5）：汉诺塔问题
（6）：青蛙跳台阶问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.接收一个整型值（无符号），按照顺序打印它的每一位。 例如： 输入：1234，输出 1 2 3 4.

code1:递归实现1 2 3 4

#if 0
//code1：递归实现1 2 3 4
void Print(unsigned int _num)
{
	//如果个位数，就可以直接打印。
	if(_num<10){
		printf("%d ",_num);
		return;
	}
	//每次递归的是商1234--》123--》12--》1
	Print(_num/10);
	//每次打印的是余数4--》3--》2--》1
	printf("%d ",_num%10);
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

code2:递归实现1 2 3 4

#if 1
//code2：递归实现1 2 3 4
void Print(unsigned int _num)
{
	//如果大于9就，就继续递归
	if(_num>9){
		Print(_num/10);
	}
	//_num>9条件不成立，数字是个位数就打印.
	//if条件满足，递归结束，返回。
	printf("%d ",_num % 10);
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13

code3:循环输出1 2 3 4

#if 1
//code3：循环输出1 2 3 4
void Print(unsigned int _num)
{
	int arr[32] = {0};
	int i = 0;
	//把所有的数单个单个存起来4 3 2 1
	while(_num>0){
		arr[i] = _num%10;
		_num = _num/10;
		i++;
	}
	//降序循环实现每个数的打印1 2 3 4
	while(i>0){
		i--;
		printf("%d ",arr[i]);
	}
	printf("\n");
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

code4:循环打印4 3 2 1

#if 1
//code4:循环打印4 3 2 1
void Print(unsigned int _num)
{
	int arr[32] = {0};
	int i = 0;
	while(_num>0){
		arr[i] = _num%10;
		printf("%d ",arr[i]);
		_num = _num/10;
		i++;
	}
	printf("\n");
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.2 编写函数不允许创建临时变量，求字符串的长度。

思路：asdf1234
asdf1234\0
1+sdf1234\0
1+1+df1234\0
1+1+1+f1234\0
1+1+1+1+1234\0
1+1+1+1+1+234\0
1+1+1+1+1+1+34\0
1+1+1+1+1+1+1+4\0
1+1+1+1+1+1+1+1+\0
1+1+1+1+1+1+1+1+0

code1：创建变量，利用下标遍历数组元素个数

#if 1
//code1：创建变量，利用下标遍历数组元素个数
int MyStrlen(const char* _arr)
{
	int i = 0;
	while(_arr[i] != '\0'){
		i++;
	}
	return i;
}
#endif
1
2
3
4
5
6
7
8
9
10
11

code2：创建变量，利用数组名遍历数组元素个数

#if 1
//code2：创建变量，利用数组名遍历数组元素个数
int MyStrlen(const char* _arr)
{
	int count = 0;
	while(*_arr != '\0'){
		//指向的是数组的下一个元素
		_arr++;
		count++;
	}
	return count;
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13

code3:递归实现

#if 1
//code3:递归实现
int MyStrlen(const char* _arr)
{
	if(*_arr == '\0'){
		return 0;
	}
	return 1+MyStrlen(_arr+1);
}
#endif
1
2
3
4
5
6
7
8
9
10

1.3 求n的阶乘。（不考虑溢出）

思路：7！
7！
76！
765！
7654！
76543！
765432！
765432*1！（1！== 1）

code1:递归实现

#if 1
//code1:递归实现
int Factorial(int _num)
{
	if(_num == 1){
		return 1;
	}
	return _num*Factorial(_num-1);
}
#endif
1
2
3
4
5
6
7
8
9
10

code2：循环实现

#if 1
//code2：循环实现
int Factorial(int _num)
{
	//5！=1*2*3*4*5
	int i = 1;
	int total = 1;
	for(;i<=_num;i++){
		total = total*i;
	}
	return total;
}
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.4 求第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*）
注：斐波那契数数列使用递归时，其属于双递归，要大量的重复计算。效率很低。因此求第n个斐波那契数不能使用递归来求。

code1:递归实现

#if 1
//code1:递归实现
int Fibonacci(int _num)
{
	if((_num==1) || (_num==2)){
		return 1;
	}
	return Fibonacci(_num-1)+Fibonacci(_num-2);
}
#endif
1
2
3
4
5
6
7
8
9
10

code2：验证递归的效率很低

#if 1
//code2：验证递归的效率很低
int count = 0;//全局变量定义在源文件中
int Fibonacci(int _num)
{
	if(_num == 3){
		count++;
	}
	if((_num==1) || (_num==2)){
		return 1;
	}
	return Fibonacci(_num-1)+Fibonacci(_num-2);
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14

code3:循环实现

#if 1
//code3:循环实现
int Fibonacci(int _num)
{
	int first = 1;
	int second = 1;
	int third = 1;
	//第三个数循环一次；第四个数循环两次。
	while(_num>2){
		//第三个数是第一个数和第二个数之和
		//第二个数就是这次的第三个数
		//第一个数就是这次的第二个数
		third = second + first;
		first = second;
		second = third;
		_num--;
	}
	return third;
}
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.练习递归

1.递归实现n的k次方
2.计算一个数的每位之和。DigitSum(n),输入一个非负整数，返回组成他的数字之和。
eg：1234–1+2+3+4=10
3.逆序打印字符串。
4.字符串逆序。

2.1 递归实现n的k次方

思路：
2^10
= 22^9
= 222^8
= 2222^7
= 22222^6
= 222222^5
= 2222222^4
= 22222222^3
= 222222222^2
= 222222222*2^1

#if 1
int NK(int _n, int _k)
{
	if(1 == _k){
		return _n;
	}
	return _n*NK(_n,_k-1);
}
#endif
1
2
3
4
5
6
7
8
9

2.2 计算一个数的每位之和。DigitSum(n),输入一个非负整数，返回组成他的数字之和。

eg：1234–1+2+3+4=10
思路：1234
123+4
12+3+4
1+2+3+4

#if 1
int DigitSum(int _n)
{
	if(_n < 10){
		return _n%10;
	}
	return _n%10 + DigitSum(_n/10);
}
#endif
1
2
3
4
5
6
7
8
9

2.3 逆序打印字符串。

思路：asdf1234
4 asdf123
43 asdf12
432 asdf1
4321 asdf
4321f asd
4321fd as
4321fds a

#if 1
void PrintReverseString(char str[])
{
	if(*str != '\0'){
		PrintReverseString(str+1);
		printf("%c \n",*str);
	}
	printf("\n");
}
#endif
1
2
3
4
5
6
7
8
9
10

2.4 字符串逆序。

思路：
1234asdf
f234asd1
fd34as21
fds4a321
fdsa4321

code1：递归实现字符串逆序

思路：asdf1234\0
	(1)a先拿出来：   *sdf1234\0
	   4放在a的位置：4sdf1234\0
	   4位置放\0:    4(sdf123\0)\0
	   将a放在\0的位置： 4(sdf123\0递归)a
	(2)(sdf123\0)
	   *df123\9
	   3df123\0
	   3(df12\0)\0
	   3(df12\0递归)s
	(3)(df12\0)
	   *f12\0
	   2f12\0
	   2(f1\0)\0
	   2(f1\0递归)d
	(4)(f1\0)
	   *1\0
	   11\0
	   1\0\0
	   1(\0递归)f	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void ReverseString(char str[])
{
	char* start = str;
	char* end = str+strlen(str)-1;
	char temp = *start;
	*start = *end;
	*end = '\0';
	//一个字符时可交换可不交换
	if(strlen(str+1)>=2){
		ReverseString(str+1);
	}
	*end = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

code2：不使用递归，正常交换进行字符串逆序。

//code1：不使用递归，正常交换进行字符串逆序。
void ReverseString(char str[])
{
	char* start = str;
	char* end = str + strlen(str) -1;
	while(start<end){
		char temp = *start;
		*start = *end;
		*end = temp;
		start++;
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.C程序地址空间

1.C程序地址空间，也就是内存空间的布局，main函数先进后出;
2.栈区地址向下增长，堆区地址向上增长。栈区属于先进后出。
3.定义一个函数或者局部变量，从main函数开始，每调一个函数向下给每一个函数创建一个栈帧。
4.函数里面的变量在开辟空间时，就是在该函数所开辟的空间中分配一片空间供该变量使用。
5.局部变量具有随函数调用而创建，函数开辟栈空间，随函数调用结束开辟空间被释放，局部变量也被释放。
6.给一个函数形成的结构，叫做栈帧，（栈中给函数开辟的空间）。
7.每个函数都有自己独立的栈帧结构，函数调用代表栈帧结构被创建，函数调用结束代表栈帧结构被释放；
函数内部的局部变量在栈帧中创建和释放，返回时栈帧由底向上弹栈，调用时，栈帧由上而下压栈的过程。