目录
一、什么是递归
（一）概念
递归是一种解决问题的方法，在C语言中，递归就是函数自己调用自己；
一个简单的演示如下：
#include <stdio.h>
int main()
{
printf("hehe\n");
main();//main函数中⼜调⽤了main函数
return 0;
}只作为简单的演示，不是为了解决问题，且代码最终也会陷入死递归，导致栈溢出（Stack overflow）；
原因：每一次函数调用，都要为这次函数调用分配内存空间，是从内存的栈区上分配的，如果无限的递归调用函数，就会将栈区空间填满（使用完），这时就出现了栈溢出的现象
（二）递归的思想
通过函数自己调用自己可以发现，递归可以把一个大型复杂问题层层转化为一个与原问题相似，但规模较小的子问题来求解，直到子问题不能再被拆分，递归就结束了；
递归是少量的代码完成了大量复杂的运算；
递归的思想就是把大事化小的过程；
递归中的"递"是递推的意思，"归"就是回归的意思；
理解如下：
二、递归的条件
递归得有限制条件，不然很容易造成死递归等错误
在书写递归代码时，有2个必要条件：
① 递归存在限制条件，当满足这个限制条件时，递归便不再继续
② 每次递归调用之后越来越接近这个限制条件
三、递归的举例
举例：求 n 的阶乘
一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1；
自然数 n 的阶乘写作 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 的阶乘都是可以通过公式计算的，公式如下：
实现代码如下：
int Fact(int n)
{
if(n==0)
return 1;
else
return n*Fact(n-1);
}测试：
#include <stdio.h>
int Fact(int n)
{
if(n==0)
return 1;
else
return n*Fact(n-1);
}
int main()
{
int n = 0;
printf("输入一个数求它的阶乘：");
scanf("%d", &n);
int ret = Fact(n);
printf("\n阶乘为：%d\n", ret);
return 0;
}结果为：
画图演示：
四、递归与迭代
（一）递归的缺陷
递归是一种很好的编程技巧，但是和很多技巧一样，也是可能被误用的，就像上面的举例一样，看到推导的公式，很容易就被写成递归的形式；
虽然用递归思想来书写代码确实可以产生正确的结果，但是在递归函数调用的过程中涉及一些运行时的开销：
在C语言中每一次函数调用，都需要为本次函数调用在内存的栈区，申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧；
函数不返回，函数对应的栈帧空间就一直占用，所以如果函数调用中存在递归调用的话，每一次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间；
所以如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出（Stack overflow）的问题
（二）迭代
所以如果不想使用递归，就得想其他的办法，通常就是迭代的方式（通常就是循环的方式），如下演示：
注：迭代是大类，循环是迭代，但迭代不一定是循环
int Fact(int n)
{
int ret = 1;
for(int i=1; i<=n; i++)
{
ret *= i;
}
return ret;
}事实上，我们看到的许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更加清晰，但是这些问题的迭代实现往往比递归实现效率更高；
当一个问题非常复杂，难以使用迭代的方式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时的开销
（三）举例体现递归与迭代的区别
例子：求第n个斐波那契数
一个斐波那契数等于前两个数之和，如：
1 1 2 3 5 8 13 21 34 55 ......
公式如下：
看到公式，很容易写成递归的形式，如下：
int Fib(int n)
{
if(n<=2)
return 1;
else
return Fib(n-1) + Fib(n-2);
}#include <stdio.h>
int main()
{
int n = 0;
printf("输入一个数，计算对应的斐波那契数：");
scanf("%d", &n);
int ret = Fib(n);
printf("\n第%d个斐波那契数为：%d\n", n, ret);
return 0;
}当我们输入 50 的时候，需要花很长的时间才能计算出结果，这是因为递归的层次太深了，冗余的计算会很多：
画图分析可看出递归深度高达50次，且每次计算都是指数型增长，这些计算是非常冗余的，所以得用迭代的方式解决；
迭代：我们知道斐波那契数的前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;
}使用迭代的方式来书写代码，效率就高出很多
五、有意思的点
（一）递推的写法
三要素：
① 变成最简单问题的限制条件
② 变得更简单的语句（调用自己）
③ 最简单的一步的语句
递推的书写过程中，三要素都齐全但没有及时回归，还是会造成栈溢出（Stack overflow）
（二）拓展学习
1、青蛙跳台问题
青蛙可以跳一个台阶or两个台阶，n个台阶有几种跳法的理解：
1个跳台：1种
2个跳台：2种——跳2次1阶为一种，跳1次2阶为一种
n个台阶：（n-1）个台阶跳上n个台阶时是一种跳法，（n-2）个台阶跳上n个台阶时是另一种跳法，所以n个台阶的跳法 = （n-1）个台阶跳法 + （n-2）个台阶跳法 ：
fib(n) = fib(n-1) + fib(n-2)——斐波那契数列
2、汉诺塔问题（儿童益智游戏）
描述：借助于B，将A上的盘子，挪到C上，挪的过程中，盘子一定是上小下大
思路：
n-1个盘子到b，最大的n移到c；
n-2个盘子到a，第二大的n-1移到c；
如此反复......
简单来说：除了最下面的盘子，其他的-1个盘子动来动去，而最下面的盘子到C
以上博客仅供分析，若有错误，请多多指正，共同进步
标签：10,return,函数,递归,int,阶乘,台阶,迭代 From： https://blog.csdn.net/m0_66277256/article/details/139249982