【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;
}
当然，这里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)在这个示意图中，从最右边的数字开始，递归调用Print函数，每次都打印出当前数字的最后一位，然后将问题规模减小，直到数字变成0为止。具体的过程如下：
- 调用Print(1024)。
- Print(1024)调用Print(102)。
- Print(102)调用Print(10)。
- Print(10)调用Print(1)。
- Print(1)调用Print(0)。
- Print(0)直接返回，不做任何处理。
- Print(1)返回，打印出1，然后返回到调用它的函数。
- Print(10)返回，打印出0，然后返回到调用它的函数。
- Print(102)返回，打印出2，然后返回到调用它的函数。
- Print(1024)返回，打印出1，然后函数执行结束。 11代码：
# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
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;
}
三、递归与迭代
3.1递归的思考
递归是一种有用的编程技巧，但像其他技巧一样，也容易被误用。举例来说，看到推导的公式，很容易就被写成递归的形式犹如数学函数一样。
int Fact(int n)
{
if(n<=0)
return 1;
else
return n*Fact(n-1);
}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;
}上述代码是能够完成任务，并且效率是?递归的?式更好的。
事实上，我们看到的许多问题是以递归的形式进?解释的，这只是因为它??递归的形式更加清晰， 但是这些问题的迭代实现往往?递归实现效率更?。 当?个问题?常复杂，难以使?迭代的?式实现时，此时递归实现的简洁性便可以补偿它所带来的运?时开销。
3.2求第n个斐波那契数
我们还可以举出更极端的例子，比如计算第n个斐波那契数，不适合使用递归求解，但是斐波那契数的问题通常是用递归的形式描述的，如下:
看到这公式，很容易想到这还不简单啊，将代码递归的形式走起，如：
int Fib(int n)
{
if(n<=2)
return 1;
else
return Fib(n-1)+Fib(n-2);
}当我们输入为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，如果递归写出的问题，是存在明显的缺陷，那就不能使用递归，得用迭代的方式处理。