遞推是什麼意思

在數學和電腦科學中，遞推（Recursion）是指一種通過使用自身定義來定義函數或運算的方法。換句話說，一個遞歸過程會在定義中調用自身，直到達到一個基本的條件（也稱為遞歸出口），這個條件會導致過程停止，並且從上一個層次返回結果。

遞歸通常用於描述某些數學結構和運算，以及用於設計電腦程式中的遞歸函數。例如，遞歸可以用來描述樹狀結構、遞歸數列（如漢諾塔問題），以及像 factorial（階乘）、 Fibonacci 數列這樣的數學函數。

在程式設計中，遞歸函數通過遞歸調用來解決問題，每次調用都帶有縮小了的問題規模。當函數遞歸調用自身時，它會保存當前狀態的資訊，以便在返回時恢復。這種保存和恢復狀態的過程通常由程式設計語言的堆棧機制來管理。

遞歸的一個例子是 factorial 函數的定義，它接受一個正整數 n 並返回從 1 到 n 的所有整數的乘積。factorial 函數可以定義為：

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

這個定義中，factorial 函數在 n 不等於 0 或 1 時調用自身，這就是遞歸的部分。當 n 為 0 或 1 時，函數返回 1，這就是遞歸出口，因為這時不需要再調用自身。

遞歸的一個優點是它可以使代碼更簡潔，更容易理解，因為它遵循了分而治之的策略。然而，遞歸函數可能會導致過度堆棧的錯誤，因為每次遞歸調用都會消耗堆棧空間，尤其是在深度遞歸的情況下。因此，在實際應用中，遞歸應該在使用時小心控制，或者使用疊代來代替，以避免潛在的性能問題。