递归方法就是直接或者间接的调用自己，它可以将一些发杂问题简化。
递归在下列方法中经常会用到：
-
定义是递归的。
如斐波拉契数列、阶乘等。
-
数据结构是递归的。
数据结构本身具有递归性，如链表、树等。
-
问题的解法是递归的。
有一类问题，虽然问题本身没有明显的递归结构，但采用递归求解比迭代求解更简单。如汉诺塔问题、八皇后问题、迷宫问题。
所有的递归都能用循环解决
分治法
在求解4!时，我们会先求解3!，然后再进一步分解进行求解，这种求解叫做分治法。
使用分治法需要满足3个条件：
- 能将一个问题转换成一个小问题，新问题和原问题的解法相同或类同。不同的只是被处理的对象，并且这些处理更小且变化是有规律的。
- 可以通过上述转换而使得问题简化。
- 必须有一个明确的递归出口，或成为递归边界。
汉诺塔问题
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。
移动圆盘时受到以下限制:
- 每次只能移动一个盘子；
- 盘子只能从柱子顶端滑出移到下一根柱子；
- 盘子只能叠在比它大的盘子上。
解决思路
我们使用递归来解决：
- n=1时，直接把盘子从A移动到C就行了。(递归边界)
- n>1时：
- 先把n-1个盘子从A移动到B；(子问题，递归)
- 将最大的盘子从A移动到C；
- 再将B上n-1个盘子移动到C。(子问题，递归)
用栈解决
static void move(LinkStack *A, LinkStack *B, LinkStack *C, int n) {
if (n == 1) {
int elem;
Pop(A, &elem);
Push(C, elem);
} else {
// 把栈A中n-1个盘子放到栈B
move(A, C, B, n - 1);
// A栈出栈放入C栈
int elem;
Pop(A, &elem);
Push(C, elem);
// 把栈B中n-1个盘子放到栈C
move(B, A, C, n - 1);
}
}
void hanoi(LinkStack *A, LinkStack *B, LinkStack *C) {
move(A, B, C, StackLength(*A));
}
int main(int argc, const char * argv[]) {
int n = 5;
LinkStack A, B, C;
InitStack(&A);
InitStack(&B);
InitStack(&C);
for (int i = n; i > 0; i--) {
Push(&A, i);
}
printf("原始栈A：");
StackTraverse(A);
printf("原始栈C：");
StackTraverse(C);
hanoi(&A, &B, &C);
printf("移动后栈A：");
StackTraverse(A);
printf("移动后栈C：");
StackTraverse(C);
return 0;
}
// 输出
原始栈A：1 2 3 4 5
原始栈C：
移动后栈A：
移动后栈C：1 2 3 4 5
移动过程
void hanoi2(char *A, char *B, char *C, int n) {
if (n == 1) {
printf("move %s to %s\n", A, C);
} else {
hanoi2(A, C, B, n - 1);
printf("move %s to %s\n", A, C);
hanoi2(B, A, C, n - 1);
}
}
int main(int argc, const char * argv[]) {
hanoi2("a", "b", "c", 3);
return 0;
}
// 输出
move a to c
move a to b
move c to b
move a to c
move b to a
move b to c
move a to c
image.png
