定义
若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接或间接地调用自己，则称这个过程是递归的过程。
递归的三种情况：定义是递归的、数据结构是递归的、问题的解法是递归的。
递归的特点：递归至少存在一个出口、函数内部自己调用自己。
问题举例
阶乘
阶乘的定义：
$$ n! = \left\{ \begin{array}{c} 1, & n = 0 \\ n \cdot (n-1)!, & n \geqslant 1 \end{array} \right.$$可知阶乘的定义是递归的。
1long long Factorial(long long n) {
2 if (n == 0) {
3 return 1;
4 }
5 else {
6 return n * Factorial(n-1);
7 }
8}
查找链表的元素
定义链表：
1struct Node {
2 ElemType data;
3 Node *next;
4};
可知链表的数据结构是递归的。
1void Search(Node *f, ElemType e) {
2 if (f != NULL) {
3 if (f->data == x) {
4 printf("%d\n", f->data);
5 }
6 else {
7 Search(f->next, e);
8 }
9 }
10 return;
11}
汉诺塔问题
问题概述：假设有3个分别命名为 $x$，$y$，$z$ 的塔座，在塔座 $x$ 上插有 $n$ 个直径大小各不相同、依次编号为 $1,2,3,…,n$ 的圆盘。现要求将 $x$ 塔座的 $n$ 个圆盘移动到 $z$ 塔座上且按同样的顺序堆叠。圆盘移动时遵循以下规则：
- 每次只能移动一个圆盘。
- 圆盘可以放在 $x$，$y$，$z$ 的任意塔座上。
- 任何时刻都不能将一个较大的圆盘放在较小的圆盘之上。
因此，汉诺塔问题的解法是递归的。
1void hanoi(int n, char x, char y, char z) {
2 if (n == 1) {
3 move(x, 1, z); // 将编号为1的圆盘从x移到z
4 }
5 else {
6 hanoi(n-1, x, z, y); // 将x上编号为1到n-1的圆盘移到y，z作为辅助塔
7 move(x, n, z); // 将编号为n的圆盘从x移到z
8 hanoi(n-1, y, x, z); // 将y上编号为1到n-1的圆盘移到z，x作为辅助塔
9 }
10}