(一)递归的含义:
在c语言中，递归就是函数自己调用自己，递归就是把大事化小的一个过程
(二)递归的限制条件:
在使用函数递归时，有两个必要条件需要满足
1.递归存在限制条件，当满足这个条件，递归便不再继续
2.每次递归调用后越来越接近这个条件
(三)递归举例:
1.使用递归的方式求一个数的阶乘
首先我们要明白什么是阶乘，一个正整数 n 的阶乘，记作n！表示从 1 到 n 所有整数相乘。 公式：n！=n×(n-1)×(n-2)×…×1。比如：
3的阶乘就是1×2×3
5的阶乘就是1×2×3×4×5
了解了阶乘，我们可以先不使用递归来完成代码，如下所示
#include <stdio.h>
int main()
{
//非递归求n的阶乘
int a = 0;
scanf("%d", &a);
int i = 0;
int sum = 1;
for (i = 1; i <=a; i++)
{
sum *= i;
}
printf("%d的阶乘是%d",a,sum);
return 0;
}
接着我们可以尝试用递归的方式来完成n的阶乘，想要使用递归，就得记住它的两个必要条件，首先要有限制条件，接着保证在每次调用函数时向终止条件靠近，否则会陷入死循环，用以下代码解释
#include <stdio.h>
//递归求n的阶乘（不考虑溢出的问题）
int jiecheng(int n)
{
if (n == 1)
{
return 1;
}
return n * jiecheng(n – 1);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret=jiecheng(n);
printf("%d", ret);
return 0;
}
上方代码中，当n==1时就是递归的终止条件，当我们需要求5的阶乘时，在主函数中输入5，5被传到jiecheng函数中，不等于1，
执行5×jiecheng(4)，jiexheng(4)不满足终止条件，
继续执行4×jiecheng(3)，jiecheng(3)不满足，
继续执行3×jiecheng(2)，jiecheng(2)不满足，
继续执行2×jiecheng(1)，jiecheng(1)满足终止条件，
jiecheng(1)=1，然后开始逐层回溯，jiecheng(2)=2×1，jiecheng(3)=3×2×1，依次类推，最终返回5×4×3×2×1，在上述递归中，每次调用函数本身都会接近限制条件，这样就是一个完整的用递归求一个数的阶乘代码
2.返回值练习
完成用递归求阶乘后，我们练习一道简单的递归问题。如下方递归函数，在调用函数返回值fun(2)，最终函数的返回值是多少
int fun(int n)
{
if(n==5)
return 2;
else
return 2*fun(n+1);
}
跟递归求阶乘一样，当n=2时，不满足终止条件n==5，
继续执行2×fun(3);
依此类推fun(3)=2×fun(4);
fun(4)=2×fun(5)=2×2;
然后逐层回溯，最终返回值是2×2×2×2=16
3.递归实现n的k次方
上述函数中都是一个参数，那么如果函数中有两个或者多个参数怎么办，其实都是一样的道理，只要满足函数递归的两个必要条件，就可以完成递归，比如使用递归求一个n的k次方，n的k次方就是k个n相乘的结果，我们可以先不使用递归完成代码，如下所示
#include <stdio.h>
// 计算 n^k
int power(int n, int k)
{
int res = 1;
for (int i = 0; i < k; i++)
{
res *= n;
}
return res;
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
printf("%d\\n", power(n, k));
return 0;
}
接着，我们使用递归的方式，如下图所示
#include <stdio.h>
double cifang(int n, int k)
{
if (k == 0)
{
return 1.0;
}
else if (k > 0)
{
return n * cifang(n, k – 1);
}
else
{
return 1.0 / cifang(n, -k);
}
}
int main()
{
int n = 0;
int k = 0;
scanf("%d %d", &n, &k);
double ret = cifang(n, k);
printf("%d的%d次方是:%f", n, k, ret);
return 0;
}
终止条件为k==1，当我们要求2的3次方时，不满足终止条件，且k>0，
执行2×cifang(2，2)；
cifang(2，2)=2×cifang(2，1)；
cifang(2，1)=2×cifang(2，0)；
此时k==0，所以cifang(2，0)=1.0，然后逐层回溯，最终结果是2×2×2×1=8 当k＜0时同理，可以自行推理一遍过程
(四)拓展递归问题
1.青蛙跳台阶
一只青蛙一次可以跳1 级或2 级台阶，求跳上 n 级台阶共有多少种跳法。
设 f(n) 为 n 级台阶的跳法数
只剩1 级：只能跳 1 步 → f(1)=1
只剩2 级：(1+1)、(2) → f(2)=2
n>2 时： 最后一步要么跳 1 级（前面剩 n−1 级），要么跳 2 级（前面剩 n−2 级） 得递推公式：f(n)=f(n−1)+f(n−2)
#include <stdio.h>
// 递归求跳法数
int jump(int n)
{
// 递归出口
if (n == 1)
return 1;
if (n == 2)
return 2;
// 递归调用
return jump(n – 1) + jump(n – 2);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", jump(n));
return 0;
}
2.汉诺塔问题
有A、B、C三根柱子，n 个从小到大叠在 A 柱。 规则：
每次只能移动一个盘子
大盘不能放在小盘上面 目标：把所有盘子从 A 移到 C，B 作为中转
#include <stdio.h>
// n:盘子数 a:起点 b:中转 c:终点
void hanoi(int n, char a, char b, char c)
{
// 递归出口：只剩1个盘
if (n == 1)
{
printf("%c -> %c\\n", a, c);
return;
}
// 1. n-1个 从a移到b，c中转
hanoi(n-1, a, c, b);
// 2. 最下面大盘 a -> c
printf("%c -> %c\\n", a, c);
// 3. n-1个 从b移到c，a中转
hanoi(n-1, b, a, c);
}
int main()
{
int n;
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
