函数递归
3.1 什么是递归？
程序调用自身的编程技巧称为递归（ recursion）
递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量
递归的主要思考方式在于：把大事化小
3.2 递归的必要两个条件
1.存在限制条件，当满足这个限制条件的时候，递归便不再继续
2.每次递归调用之后越来越接近这个限制条件
3.2.1 练习1：
接受一个整型值（无符号），按照顺序打印它的每一位 。例如：输入：1234 输出 1 2 3 4
代码演示：
define _CRT_SECURE_NO_WARNINGS
include<stdio.h>
//%d 是打印有符号的整数(会有正负数)
//%u 是打印无符号的整数
//接受一个整型值（无符号），按照顺序打印它的每一位。
//例如：输入：1234 输出 1 2 3 4
void print(unsigned int n)
{
if (n > 9)
{
print(n/10);
}
printf("%d ", n % 10);}
int main()
{
unsigned int num=0;
scanf("%u", &num);
print(num);//接受一个整型值（无符号），按照顺序打印它的每一位。
return 0;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
运行结果：
图解：
注意：1. 存在限制条件，当满足这个限制条件的时候，递归便不再继续，没有限制条件会出现死递归
- 每次递归调用之后越来越接近这个限制条件
3.2.2 练习2：
编写函数不允许创建临时变量，求字符串的长度
也就是让我们模拟strlen函数功能功能
代码演示：创建了临时变量count来计数
define _CRT_SECURE_NO_WARNINGS
//模拟实现strlen
include<stdio.h>
//int my_strlen(char str[]) 参数部分写成数组形式
int my_strlen(char* str)//参数部分写成指针形式
{
int count = 0;
while (*str != '\0')//解引用找到字符
{
count++;
str++;//找下一个字符，每个字符一个字节
}
return count;}
int main()
{
char arr[] = "abc";
//char*
int len = my_strlen(arr);
printf("%d\n", 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
不允许创建临时变量，我们考虑用 递归
递归求解：我们求’abc\0’的长度，如果第一个字符不是’\0’,那我们就可以求1+’bc\0‘的长度，即：第一个字符不是’\0’,就可以拆开
my_strlen(“abc”)
1+my_strlen(“bc”)
1+1+my_strlen(“c”)
1+1+1+my_strlen(" ")
1+1+1+0
代码演示：
define _CRT_SECURE_NO_WARNINGS
include<stdio.h>
int my_strlen(char* str)//参数部分写成指针形式
{
if (*str != '\0')
return 1 + my_strlen(str + 1);//str++不可以，传进去的还是a地址
else
return 0;}
int main()
{
char arr[] = "abc";
//char*
int len = my_strlen(arr);
printf("%d\n", len);//3
return 0;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
图解：
- 递归与迭代
4.1练习：
求n的阶乘。（不考虑溢出）
代码演示：
define _CRT_SECURE_NO_WARNINGS
include<stdio.h>
递归实现
//int fac(int n)
//{
// if (n<=1)
// return 1;
// else
// return n*fac(n-1);
//}
//迭代实现
int fac(int n)
{
int i = 0;
int ret = 1;
for (i = 1; i <= n; i++)
{
ret *= i;
}
return ret;}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = fac(n);
printf("ret = %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
4.2练习：
求第n个斐波那契数。（不考虑溢出）
递归解决代码演示：
define _CRT_SECURE_NO_WARNINGS
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("ret = %d\n", ret);
printf("%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
运行结果：
分析:使用递归会重复大量的运算,求第40个斐波那契数的时候，第3个斐波那契数就被重复了39088169次，效率很低，不推荐用递归解决
那如何解决上述的问题?
将递归改写成非递归
使用static对象替代nonstatic局部对象。在递归函数设计中，可以使用static对象替代nonstatic局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销，而且static对象还可以保存递归调用的中间状态，并且可为各个调用层所访问
迭代解决代码演示：
define _CRT_SECURE_NO_WARNINGS
include<stdio.h>
//迭代实现
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 0;
while (n >= 3)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;//n=1 n=2时返回c
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("ret = %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
分析:1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰
- 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些
- 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销
