溫馨提示×

如何在c++中使用stack類實(shí)現(xiàn)遞歸

c++
小樊
81
2024-09-25 07:21:12
欄目: 編程語言

在C++中，使用stack類實(shí)現(xiàn)遞歸的方法是將函數(shù)的返回地址和參數(shù)壓入棧中，然后在遞歸調(diào)用結(jié)束后，從棧中彈出這些值并恢復(fù)調(diào)用者的狀態(tài)。這里是一個(gè)簡單的示例，展示了如何使用stack類實(shí)現(xiàn)遞歸計(jì)算階乘：

#include <iostream>
#include <stack>

using namespace std;

// 計(jì)算階乘的函數(shù)
unsigned long long factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }

    // 創(chuàng)建一個(gè)棧對象
    stack<unsigned long long> s;

    // 將參數(shù)壓入棧中
    s.push(n);

    // 遞歸調(diào)用
    unsigned long long result = factorial(n - 1);

    // 從棧中彈出參數(shù)并恢復(fù)調(diào)用者的狀態(tài)
    n = s.top();
    s.pop();

    // 返回階乘結(jié)果
    return n * result;
}

int main() {
    int n = 5;
    cout << "Factorial of "<< n << " is: " << factorial(n) << endl;
    return 0;
}

在這個(gè)示例中，我們使用stack類來保存factorial函數(shù)的參數(shù)和返回地址。當(dāng)遞歸調(diào)用發(fā)生時(shí)，我們將參數(shù)壓入棧中，并在遞歸調(diào)用結(jié)束后從棧中彈出這些值。這樣，我們可以實(shí)現(xiàn)遞歸計(jì)算階乘的功能。

0 踩