遞歸簡介

什么是遞歸？遞歸=遞推+回歸，類似于數學歸納法，屬于分治法的應用，是數學與計算科學領域的重要思想，在離散數學、數據結構中起到了重要基礎作用，是處理與問題規模無關、結構自相似性問題的必需工具。

不要對遞歸感到恐懼，應該把遞歸當做工具而非累贅。如果實在難以理解，請先復習高中學習的數學歸納法，并善用VSCode、CLion的并行堆棧和并行監視功能，這些工具都有利于學習遞歸。

題目描述

有3個柱子，分別為from,buffer,to;最初from柱上有N個盤子，且小盤必須只能放在大盤上，反向則不可以。注意from,buffer,to的角色是相對而言的。

若N=1，則直接將盤子從from移動到to上。(遞歸基)

若N!=1：

1.則將N-1個盤子先看成一個整體，目的是將N-1個盤子借助to柱移動到buffer柱上。由于柱子的角色是相對而言的，所以此時在此過程中，from柱不變，buffer柱為原to柱，to柱為原buffer柱。

2.現在已將放在第N個盤子上的N-1個盤子全部轉移到buffer柱上(相對于整體目標而言），等效于回到了N=1的情況，直接將第N個盤子從from柱上移動到to柱上。

3.現在需要將在buffer柱上的N-1個盤子借助from柱移動到to柱上。同理，柱子的角色是相對而言的，在此過程中，原buffer柱變為from柱，原from柱變為buffer柱，原to柱不變。

在N-1的時候函數在不斷調用自己，每次都在等待上一次操作完畢（第N個盤子在等待第N-1個盤子移動完畢，第N-1個盤子又在等待第N-2個盤子移動完畢....），這是很經典的遞歸思想的問題。

切記遞歸思想只能通過找規律實現，窮舉(暴力)通常是不可行的。

代碼實現

#include <stdio.h>
void Hanio(int n, char from, char buffer, char to) {
    if (n == 1) {
        printf("%d:%c -> %c\n", n, from, to); // 輸出移動步驟
    } else {
        Hanio(n - 1, from, to, buffer); // 將 n-1 個圓片從 from 經由 to 移到 buffer
        printf("%d:%c -> %c\n", n, from, to); // 輸出移動步驟
        Hanio(n - 1, buffer, from, to);// 將 n-1 個圓片從 buffer 經由 from 移到 to
    }
}
int main() {
    int n;
    char from, to, buffer;
    /*數量、ori、goal、buffer:*/
    scanf("%d %c %c %c", &n, &from, &to, &buffer);// 輸入漢諾塔的圓片數量和起始、目的、過渡柱
    Hanio(n, from, buffer, to);// 調用漢諾塔函數
    return 0;
}