数据结构与算法9-递归

递归方法就是直接或者间接的调用自己，它可以将一些发杂问题简化。

递归在下列方法中经常会用到：

• 定义是递归的。

如斐波拉契数列、阶乘等。

• 数据结构是递归的。

数据结构本身具有递归性，如链表、树等。

• 问题的解法是递归的。

有一类问题，虽然问题本身没有明显的递归结构，但采用递归求解比迭代求解更简单。如汉诺塔问题、八皇后问题、迷宫问题。

所有的递归都能用循环解决

分治法

在求解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