遞歸方法就是直接或者間接的調(diào)用自己，它可以將一些發(fā)雜問題簡化。

遞歸在下列方法中經(jīng)常會(huì)用到：

• 定義是遞歸的。

如斐波拉契數(shù)列、階乘等。

• 數(shù)據(jù)結(jié)構(gòu)是遞歸的。

數(shù)據(jù)結(jié)構(gòu)本身具有遞歸性，如鏈表、樹等。

• 問題的解法是遞歸的。

有一類問題，雖然問題本身沒有明顯的遞歸結(jié)構(gòu)，但采用遞歸求解比迭代求解更簡單。如漢諾塔問題、八皇后問題、迷宮問題。

所有的遞歸都能用循環(huán)解決

分治法

在求解4!時(shí)，我們會(huì)先求解3!，然后再進(jìn)一步分解進(jìn)行求解，這種求解叫做分治法。

使用分治法需要滿足3個(gè)條件：

• 能將一個(gè)問題轉(zhuǎn)換成一個(gè)小問題，新問題和原問題的解法相同或類同。不同的只是被處理的對(duì)象，并且這些處理更小且變化是有規(guī)律的。
• 可以通過上述轉(zhuǎn)換而使得問題簡化。
• 必須有一個(gè)明確的遞歸出口，或成為遞歸邊界。

漢諾塔問題

在經(jīng)典漢諾塔問題中，有 3 根柱子及 N 個(gè)不同大小的穿孔圓盤，盤子可以滑入任意一根柱子。一開始，所有盤子自上而下按升序依次套在第一根柱子上(即每一個(gè)盤子只能放在更大的盤子上面)。

移動(dòng)圓盤時(shí)受到以下限制:

• 每次只能移動(dòng)一個(gè)盤子；
• 盤子只能從柱子頂端滑出移到下一根柱子；
• 盤子只能疊在比它大的盤子上。

解決思路
我們使用遞歸來解決：

• n=1時(shí)，直接把盤子從A移動(dòng)到C就行了。(遞歸邊界)
• n>1時(shí)：
  • 先把n-1個(gè)盤子從A移動(dòng)到B；(子問題，遞歸)
  • 將最大的盤子從A移動(dòng)到C；
  • 再將B上n-1個(gè)盤子移動(dòng)到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個(gè)盤子放到棧B
        move(A, C, B, n - 1);
        // A棧出棧放入C棧
        int elem;
        Pop(A, &elem);
        Push(C, elem);
          // 把棧B中n-1個(gè)盤子放到棧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("移動(dòng)后棧A：");
    StackTraverse(A);
    printf("移動(dòng)后棧C：");
    StackTraverse(C);
    
    return 0;
}
// 輸出
原始棧A：1 2 3 4 5 
原始棧C：
移動(dòng)后棧A：
移動(dòng)后棧C：1 2 3 4 5 

移動(dòng)過程

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