学习笔记 | C 语言函数递归
什么是递归？
首先在C语言中，递归发生在函数中，递归是一种解决问题的方案，函数自己调用自己。
最简单的递归举例：
#include <stdio.h>
int main()
{
printf("digui\n");
main();
return 0;
}
执行逻辑如下：
程序会进入死循环，最终崩溃（Stack overflow 栈溢出）。这只是递归的演示，但算是错误示范。
递归的思想：
把一个复杂的问题转化为一个与原问题相似，但规模较小的子问题来求解；直到子问题不能再被拆分，递归结束。核心思想就是大事化小。
递归中递就是递推，归就是回归的意思。
递归的限制条件：
- 递归存在限制条件，当满足这个限制条件的时候，递归便不再继续。
- 每次递归调用之后越来越接近这个限制条件。
举例1：求 n 的阶乘（不考虑溢出）
例如：5！= 1 * 2 * 3 * 4 * 5
可以拆成：n! = n * (n - 1)!
比如：
5！ = 5 * 4！
= 5 * 4 * 3！
函数公式如下：
Fact(n) = n * Fac(n-1)
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;
}
执行逻辑
绿色箭头表示层层递推、递推到满足限制条件；红色箭头表示回归，也是一层层返回。
这里需要注意，递推过程中return语句是没有返回值的，他的计算一直在等函数的返回，直到抵达条件并开始回归时，自底向上才会一层层返回值，此时return语句才有了返回值。
重新看一下之前的限制条件，这也是必要条件：
- 递归存在限制条件，当满足这个限制条件的时候，递归便不再继续。
- 每次递归调用之后越来越接近这个限制条件。
简单理解，函数递归就是自己调用自己，调用时必须设置条件，随着调用次数增加，越来越接近这个条件限制，当满足条件时递归不再继续。
举例2：顺序打印一个整数的每一位
解题思路：
printf(1234)
= printf(123) + 4
= print(12) + 3
以此类推
void Print(int n)
{
if(n>9)
Print(n/10);
printf("%d ",n%10);
}
int main()
{
int n = 0;
scanf("%d",&n);
Print(n);
return 0;
}
递归与迭代
在C语言中每一次函数调用，都要为本次函数调用在栈区申请一块儿内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。
函数不返回，函数对应的栈帧空间一直占用。所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也会可能引起栈溢出（Stack over flow）问题。
将n!问题使用迭代方式解决
int main()
{
int n = 0;
scanf("%d", &n);
int i = 0;
int ret = 1;
for (i = 1; i <= n; i++)
{
ret = ret * i;
}
printf("%d\n", ret);
return 0;
}
使用迭代相比递归是更简单的，通常来说迭代比递归有更高的效率；对于公式的理解上，递归可能更贴切，所以一般在难以使用迭代方式实现时，可以使用递归来实现。有点像SQL语句无法实现需求时，可以使用存储过程，当然，存储过程也无法实现，那就要上代码了！
举例3：求第N个斐波那契数列
前两个数字相加都等于第三个数
公式如下：
1 n <= 2
Fib(n-1)+Fib(n-2) n > 2
代码如下：
int Fib(int n)
{
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("%d\n", ret);
return 0;
}
执行结果
当求第50个斐波那契数时，程序运行非常缓慢，而且我的笔记本风扇开始疯狂运转。
修改一下代码，当计算第40位时，3 被计算了多少次
int count = 1;
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("%d\n", ret);
printf("count = %d\n",count);
return 0;
}
执行结果
使用迭代方式实现
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;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
执行结果
虽然结果有误，但是执行是非常快的
递归经典问题：
- 汉诺塔问题
- 青蛙跳台阶
这两个有空在研究。。。