遞歸方法就是直接或者間接的調(diào)用自己拧抖，它可以將一些發(fā)雜問題簡化煤搜。
遞歸在下列方法中經(jīng)常會用到：
-
定義是遞歸的。
如斐波拉契數(shù)列唧席、階乘等擦盾。
-
數(shù)據(jù)結(jié)構(gòu)是遞歸的嘲驾。
數(shù)據(jù)結(jié)構(gòu)本身具有遞歸性，如鏈表迹卢、樹等辽故。
-
問題的解法是遞歸的。
有一類問題腐碱，雖然問題本身沒有明顯的遞歸結(jié)構(gòu)誊垢，但采用遞歸求解比迭代求解更簡單。如漢諾塔問題症见、八皇后問題喂走、迷宮問題。
所有的遞歸都能用循環(huán)解決
分治法
在求解4!時谋作，我們會先求解3!缴啡，然后再進(jìn)一步分解進(jìn)行求解，這種求解叫做分治法瓷们。
使用分治法需要滿足3個條件：
- 能將一個問題轉(zhuǎn)換成一個小問題业栅，新問題和原問題的解法相同或類同。不同的只是被處理的對象谬晕，并且這些處理更小且變化是有規(guī)律的碘裕。
- 可以通過上述轉(zhuǎn)換而使得問題簡化。
- 必須有一個明確的遞歸出口攒钳，或成為遞歸邊界帮孔。
漢諾塔問題
在經(jīng)典漢諾塔問題中，有 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
