文章目录
欢迎讨论：如有错误或不足，欢迎指正和建议，本人主打“听劝”。当然，如有疑问，也期待你在评论区留言互动。
点赞＋关注：如果这篇文章对你有帮助，那就支持一下小编吧~~
1.什么是递归？
- 程序调用自身的编程技巧称为递归（ recursion）。
- 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的。
- 一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略。
- 只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
- 递归的主要思考方式在于：把大事化小。
2.递归的两个必要条件
- 存在限制条件，当满足这个限定条件的时候，递归停止。
- 每次递归调用后越来越接近这个限制条件。
代码示例
我们来看一个简单的递归代码
编写函数不允许创建临时变量，求字符串的长度。
#incude <stdio.h>
int Strlen(const char*str)
{
if(*str == '\0')
return 0;
else
return 1+Strlen(str+1);
}
int main()
{
char *p = "abcdef";
int len = Strlen(p);
printf("%d\n", len);
return 0;
}
这里的限制条件就是
str == ‘\0’
递归式为
Strlen(str+1)
不难发现，函数每次调用都会慢慢接近这个条件。
3.两个例题（阶乘和斐波那契）
求n的阶乘。（不考虑溢出）
#include<stdio.h>
int factorial(int x)
{
if (x <= 1)
return 1;
else
return x * factorial(x - 1);
}
int main()
{
int n = 0;
int m = 0;//n的阶乘的值
scanf("%d", &n);
m = factorial(n);
printf("%d", m);
}
求第n个斐波那契数。（不考虑溢出）
#include<stdio.h>
int fib(int x)
{
if (x <= 2)
return 1;
else
return fib(x - 2) + fib(x - 3);
}
int main()
{
int n = 0;
scanf("%d", &n);
int m = fib(n);
printf("%d", m);
}
发现问题
仔细思考一下这两个代码，你发现了什么？
没错，这两个代码都会出现同样的问题——当n过大时，就会出错。
- 在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。
- 使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。
为什么呢？
我们发现 fib 函数在调用的过程中很多计算其实在一直重复。
我们来看看fib（3）被计算过多少次
int count = 0;//全局变量
int fib(int n)
{
if(n == 3)
count++;
if (n <= 2)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
最后我们输出看看count，是一个很大很大的值。
那我们如何改进呢？
stack overflow（栈溢出）
- 在调试 factorial 函数的时候，如果你的参数比较大，那就会报错： stack overflow（栈溢出）这样的信息。
- 系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。
那如何解决上述的问题：
- 将递归改写成非递归。
- 使用static对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。
常规写法（迭代）
比如，下面代码就采用了，非递归的方式(迭代)来实现：
//求n的阶乘
#include<stdio.h>
int main()
{
int n = 0, m = 1;//m为n阶乘的值。注意初始化值必须为1，因为是累乘。
int i = 0;
scanf("%d", &n);
for (i = 2; i <= n; i++) {
m *= i;
}
printf("%d", m);
}
//求第n个斐波那契数
#include<stdio.h>
int main()
{
int n = 0;
scanf("%d", &n);
int a = 1;
int b = 1;
int c = 0;
if (n < 3)
n = 1;
else {
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
n = c;
}
printf("%d", n);
}
4. 递归与迭代相比较
- 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
- 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
- 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。