在認識堆疊之後，很自然地，我們會接觸到一個與堆疊緊密相關的概念——遞迴。遞迴是一種演算法策略，其中一個函數通過直接或間接地呼叫自身來解決問題。這種方法的效能往往依賴於堆疊，因為每次函數呼叫都會在堆疊上保存其狀態。

什麼是遞迴？
遞迴是一種解決問題的方法，它把問題分解為更小的子問題，直到這些子問題可以直接解決。遞迴函數在其定義中呼叫自己，通常用於解決那些可以通過解決較小實例來解決的問題。

遞迴的基礎
以下是一個簡單的遞迴函數，計算數字的階乘：

#include <iostream>

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n-1);
}

int main() {
    int num = 5;
    std::cout << "Factorial of " << num << " is: " << factorial(num) << std::endl; // 顯示 120
    return 0;
}

堆疊和遞迴
當一個函數呼叫時，其變數、參數和內部使用的資源都存儲在堆疊中。如果函數是遞迴的，那麼每次函數呼叫都會將一個新的層次加到堆疊上。過深的遞迴可能會導致堆疊溢出，這是因為堆疊的空間是有限的。

以堆疊模擬遞迴
雖然遞迴提供了解決問題的清晰方法，但有時直接使用堆疊模擬遞迴的行為可能更有利於性能。這被稱為遞迴到迭代的轉換。

以計算階乘為例，以下是一個使用堆疊模擬遞迴的例子：

#include <iostream>
#include <stack>

int factorial(int n) {
    std::stack<int> s;
    int result = 1;

    while (n > 1) {
        s.push(n);
        n--;
    }

    while (!s.empty()) {
        result *= s.top();
        s.pop();
    }

    return result;
}

int main() {
    int num = 5;
    std::cout << "Factorial of " << num << " is: " << factorial(num) << std::endl; // 顯示 120
    return 0;
}

總結
遞迴是一個非常強大的工具，尤其是在解決分而治之類型的問題時。然而，遞迴也有其缺點，特別是當深度很大時，可能會導致堆疊溢出。在這種情況下，了解如何使用堆疊直接模擬遞迴可以幫助我們更高效地解決問題。