【C语言】函数的系统化精讲（三）

---

一、递归举例

.通过上回（【C语言】函数的系统化精讲（二））我们了解到递归的限制条件，递归在书写的时候，有2个必要条件：
递归在书写时有两个必要条件：
• 递归必须有一个限制条件，当满足该条件时，递归停止。
• 每次递归调用后，逼近该限制条件。
下面我们来进行递归举例，更加深刻了解一下吧！

二、递归举例

2.1求n的阶乘

计算n的阶乘（不考虑溢出），n的阶乘就是1~n的数字累积相乘。
分析：
我们知道n的阶乘的公式： n！ = n ∗ (n − 1)!

比如：
5！= 5 * 4 * 3 * 2 * 1
4! = 4 * 3 * 2 * 1
所以我们可以直接：5！=5* 4！
这样思考的话，我们就可以把一个大的问题，转换成一个规模较小，又与原问题相似问题来进行求解！

再稍微分析⼀下，当 n<=0 的时候，n的阶乘是1，其余n的阶乘都是可以通过上述公式计算。
n的阶乘的递归公式如下：

代码：

int Fact(int n)
{
	if (n <= 0)
		return 1;
	else
		return n * Fact(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fact(n);
	printf("%d\n", ret);
	return 0;
}

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

当然，这里n的值不考虑太大的情况，n太大，会导致栈溢出，

2.2 顺序打印⼀个整数的每⼀位

输⼊⼀个整数m，打印这个按照顺序打印整数的每⼀位。
⽐如：
输⼊：1024 输出：1 0 2 4
输⼊：520 输出：5 2 0
分析：

首先，我们看1024，怎么得到这个数的每⼀位呢？
1024%10就能得到4，然后1024/10得到102，这就相当于去掉了4
然后继续对102%10，就得到了2，再除10去掉2，以此类推
不断的 %10 和 \10 操作，直到1234的每⼀位都得到；
但是这⾥有个问题就是得到的数字顺序是倒着的
但是我们有了灵感，我们发现其实⼀个数字的最低位是最容易得到的，通过%10就能得到
那我们假设想写⼀个函数Print来打印n的每⼀位，如下表⽰：

Print(1024)
   |
   └── Print(102)
             |
             └── Print(10)
                       |
                       └── Print(1)
                                 |
                                 └── Print(0)
1
2
3
4
5
6
7
8
9

在这个示意图中，从最右边的数字开始，递归调用Print函数，每次都打印出当前数字的最后一位，然后将问题规模减小，直到数字变成0为止。具体的过程如下：

1. 调用Print(1024)。
2. Print(1024)调用Print(102)。
3. Print(102)调用Print(10)。
4. Print(10)调用Print(1)。
5. Print(1)调用Print(0)。
6. Print(0)直接返回，不做任何处理。
7. Print(1)返回，打印出1，然后返回到调用它的函数。
8. Print(10)返回，打印出0，然后返回到调用它的函数。
9. Print(102)返回，打印出2，然后返回到调用它的函数。
10. Print(1024)返回，打印出1，然后函数执行结束。
    11代码：

# define _CRT_SECURE_NO_WARNINGS 1
#include 

void Print(int n)
{
	if (n > 9)
	{
		Print(n / 10);
	}
	printf("%d ", n % 10);
}
int main()
{
	int m = 0;
	scanf("%d", &m);
	Print(m);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、递归与迭代

3.1递归的思考

递归是一种有用的编程技巧，但像其他技巧一样，也容易被误用。举例来说，看到推导的公式，很容易就被写成递归的形式犹如数学函数一样。

int Fact(int n)
{
 	if(n<=0)
 	return 1;
 	else
 	return n*Fact(n-1);
}
1
2
3
4
5
6
7

Fact函数是可以产⽣正确的结果，但是在递归函数调⽤的过程中涉及⼀些运⾏时的开销。
什么是运行时的开销呢？
在C语言中，每次函数调用都需要在栈区为本次函数调用申请一块内存空间，用来保存函数调用期间的各种局部变量的值。这块空间被称为运行时堆栈，或者函数栈帧。如果函数没有返回，对应的栈帧空间就会一直被占用。因此，如果函数调用中存在递归调用，每次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。因此，如果采用函数递归的方式完成代码，递归层次太深就会浪费太多的栈帧空间，也可能引起栈溢出（stack overflow）的问题。

所以如果不想使用递归就得想其他的办法，通常就是迭代的方式（通常就是循环的方式）。
⽐如：计算n的阶乘，也是可以产⽣1~n的数字累计乘在⼀起的。

int Fact(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 = Fact(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

上述代码是能够完成任务，并且效率是⽐递归的⽅式更好的。
事实上，我们看到的许多问题是以递归的形式进⾏解释的，这只是因为它⽐⾮递归的形式更加清晰，
但是这些问题的迭代实现往往⽐递归实现效率更⾼。
当⼀个问题⾮常复杂，难以使⽤迭代的⽅式实现时，此时递归实现的简洁性便可以补偿它所带来的运⾏时开销。

3.2求第n个斐波那契数

我们还可以举出更极端的例子，比如计算第n个斐波那契数，不适合使用递归求解，但是斐波那契数的问题通常是用递归的形式描述的，如下:

看到这公式，很容易想到这还不简单啊，将代码递归的形式走起，如：

int Fib(int n)
{
 	if(n<=2)
 	return 1;
 	else
 	return Fib(n-1)+Fib(n-2);
}
1
2
3
4
5
6
7

当我们输入为50时，光标还在闪烁需要很长时间才能算出结果，这个计算所花费的时间，是我们很难接受的，这也说明递归的写法是非常低效的，那是为什么呢？

此时程序并没有停止，而是不断的计算，我们可以Ctrl+Shift+Esc打开任务管理器，我们可以看到我们的程序的CPU占比13.7%（这个13.7%不是最高的），（由于代码运行起来后，电脑便会风扇转起，直接CPU干起来，博主电脑无法立刻截不了图，所以导致截图不到想要的高CPU运行百分比，推荐你们也可以尝试一下）

其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计算，⽽且递归层次越深，冗余计算就会越多。

这里我们发现，在计算第40个斐波那契数时，使用递归方式会导致第3个斐波那契数被重复计算了39088169次，这些计算是非常冗余的。因此，斐波那契数的计算采用递归是非常不明智的，我们应该考虑使用迭代的方式来解决。
我们知道斐波那契数的前2个数都是1，然后前2个数相加就是第3个数，那么我们从前往后，从小到大计算就可以了。

这样就有下⾯的代码
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

递归虽好，但是也会引⼊⼀些问题，所以我们⼀定不要迷恋递归，适当就好。
递归和循环的选择：
1，如果使用递归写代码，非常容易，写出的代码没问题，那就使用递归。
2，如果递归写出的问题，是存在明显的缺陷，那就不能使用递归，得用迭代的方式处理。