遞迴的意思

遞迴（Recursion）是一種程式設計的技術，它允許函數自己呼叫自己。在遞迴過程中，當滿足某個條件時，遞迴會停止，並且返回到上一層的呼叫。這種技術可以用來解決許多問題，尤其是在處理遞歸結構（如樹狀結構或堆疊）時。

遞迴有幾個關鍵部分：

1. 遞迴函數：這是能夠自己呼叫自己的函數。
2. 基線情況：這是一個終止條件，當遞迴函數遇到這個條件時，它會停止遞迴，並返回一個值。
3. 遞迴步驟：這是遞迴函數在遇到基線情況之前需要執行的步驟。通常，這些步驟會包括對自身的一個呼叫。

例如，考慮一個計算整數階層的遞迴函數。階層是指一個數字除以它自己直到得到1為止的步驟數。例如，階層(15)是2，因為15 ÷ 5 = 3，5 ÷ 5 = 1。這個函數可以這樣定義：

def hanoi(n, source, auxiliary, destination):
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return
    else:
        hanoi(n-1, source, destination, auxiliary)
        print(f"Move disk {n} from {source} to {destination}")
        hanoi(n-1, auxiliary, source, destination)

這個函數的基線情況是當n為1時，它直接列印出移動盤子的信息，然後返回。在遞迴步驟中，函數會呼叫自身，減少盤子的數量，然後在完成一次移動後，再次呼叫自身來完成剩餘的移動。

遞迴的一個重要特點是它會在堆疊中保存狀態，這意味著每次遞迴呼叫都會增加堆疊的深度。這可能會導致效率問題，尤其是在處理大量數據時。因此，在實際應用中，遞迴通常會轉換為疊代形式，以減少堆疊開銷。