一、定义
一个函数自己直接或间接调用自己。
递归是用栈来实现的。
例1：死递归：内部不停地压栈、出栈，但是找不到出口。
#include <stdio.h>
void f();
void g();
void k();
void f()
{
printf("f\n");
g();
}
void g()
{
printf("g\n");
k();
}
void k()
{
printf("k\n");
f();
}
int main(void)
{
f();
return 0;
}
例2：不同函数之间的相互调用
#include <stdio.h>
void f();
void g();
void k();
void f()
{
printf("f\n");
g();
}
void g()
{
printf("g\n");
k();
}
void k()
{
printf("k\n");
}
int main(void)
{
f();
return 0;
}
例3：不同函数之间的相互调用
#include <stdio.h>
void f();
void g();
void k();
void f()
{
printf("fff\n");
g();
printf("111f\n");
}
void g()
{
printf("ggg\n");
k();
printf("222g\n");
}
void k()
{
printf("kkk\n");
}
int main(void)
{
f();
return 0;
}
例4：函数自己调用自己
#include <stdio.h>
void f(int);
void f(int n)
{
if(n == 1)
{
printf("fff\n");
}
else
{
f(n-1); // 自己调用自己，得有一个条件限制；否则，一直不停地调用自己，就陷入了死递归
}
}
int main(void)
{
f(3);
return 0;
}
二、举例
1、求阶乘
（1）用循环来实现：
#include <stdio.h>
int main()
{
int val = 0;
int i, mult = 1;
printf("请输入一个数字：\n");
printf("val = ");
scanf("%d", &val);
for(i = 1; i<=val; i++)
{
mult = mult * i;
}
printf("%d的阶乘是：%d\n", val, mult);
return 0;
}
（2）用递归来实现：
#include <stdio.h>
// 假定n>=1
long f(long n)
{
if(1 == n)
{
return 1;
}
else
{
return f(n-1)*n;
}
}
int main(void)
{
printf("%ld\n", f(5));
return 0;
}
2、使用递归求1+2+3+...+100的和
#include <stdio.h>
long sum(int n)
{
if(1 == n)
{
return 1;
}
else
{
return n + sum(n-1);
}
}
int main(void)
{
printf("%ld\n", sum(100));
return 0;
}
3、汉诺塔
思想：
先把A柱子上的前n-1个盘子借助C移到B；
再将A柱子上的第n个盘子直接移到C；
最后将B柱子上的n-1个盘子借助A移到C。
程序：
#include <stdio.h>
/*
A：初始放的柱子
B：借助的柱子
C：最后放的柱子
*/
void hanoi(int n, char A, char B, char C)
{
if(1 == n)
{
printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);
}
else
{
hanoi(n-1, A, C, B);
printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);
hanoi(n-1, B, A, C);
}
}
int main(void)
{
char ch1 = 'A';
char ch2 = 'B';
char ch3 = 'C';
int n = 0;
printf("请输入要移动的盘子的个数：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C'); // n个盘子，从A借助B移到C
return 0;
}
汉诺塔不是线性递归，而是非线性递归。
n=1时，移动1次；
n=2时，移动3次；
n=3时，移动7次；
n=64时，移动2^64-1次。
汉诺塔的复杂度是2^n-1。
问题很复杂，但是核心代码就3行。
4、走迷宫
三、 函数的调用
1、当在一个函数A的运行期间调用另一个函数B时，在运行被调函数B之前，系统需要完成三件事：
（1）将所有的实际参数、返回地址（下一条语句的地址）等信息传递给被调函数B保存。
（2）为被调函数B的局部变量（也包括形参）分配存储空间。
（3）将控制转移到被调函数B的入口。
2、从被调函数B返回主调函数A之前，系统也要完成三件事：
（1）保存被调函数B的返回结果
（2）释放被调函数B所占的存储空间（静态存储空间）
（3）依照被调函数B保存的返回地址将控制转移到调用函数A
例：
#include <stdio.h>
int f(int n)
{
n += 2;
return n;
}
int main(void)
{
int val = 0;
val = f(5);
printf("val = %d\n", val);
return 0;
}
例：
#include <stdio.h>
int f(int n)
{
n = g(n);
return n;
}
int g(int m)
{
m = m*2;
return m;
}
int main(void)
{
int val = 0;
val = f(5);
printf("val = %d\n", val);
return 0;
}
3、当有多个函数相互调用时，按照“后调用先返回”的原则，函数之间信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作；每当一个函数退出时，就释放它的存储区，进行出栈操作；当前运行的函数永远都在栈顶位置。
4、一个函数为什么可以自己调用自己？
A函数调用A函数，和A函数调用B函数，在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已！
四、递归必须满足的3个条件
1、递归必须得有一个明确的中止条件
2、该函数所处理的数据规模必须在递减（递归的值可以递增）
3、这个转化必须是可解的
某个问题是否可以用递归来解决，是一个数学问题。
例：递归的值虽然在递增，但是规模是递减的
#include <stdio.h>
int f(int n)
{
if(n>7)
{
printf("哈哈\n");
}
else
{
n = f(n+1);
}
return n;
}
int main(void)
{
int val = 0;
val = f(5);
printf("val = %d\n", val);
return 0;
}
五、循环和递归
理论上，所有的循环都可以转化成递归。但是，用递归可以解决的问题，不一定可以用循环来解决。
循环转化成递归的方法有很多，是个数学问题。
《递归论》
递归和循环的优缺点
六、递归的应用
树和森林就是以递归的方式定义的。
树和图的很多算法都是以递归来实现的。
很多数学公式就是以递归的方式定义的。
（如：斐波拉契序列）
