#include <iostream>
using namespace std;
// 遞歸計(jì)算階乘
unsigned long long factorialRecursive(int n) {
    // 基本情況
    if (n == 0) {
        return 1;
    }
    // 遞歸步驟
    return n * factorialRecursive(n - 1);
}
int main() {
    int num = 10;
    cout << num << "! = " << factorialRecursive(num) << endl;
    return 0;
}

#include <iostream>
using namespace std;
// 迭代計(jì)算階乘
unsigned long long factorialIterative(int n) {
    unsigned long long result = 1;
    // 使用for循環(huán)進(jìn)行迭代
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}
int main() {
    int num = 10;
    cout << num << "! = " << factorialIterative(num) << endl;
    return 0;
}

// 遞歸實(shí)現(xiàn)斐波那契數(shù)列
int fibonacciRecursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// 迭代實(shí)現(xiàn)斐波那契數(shù)列
int fibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }
    int prev_prev = 0; // F(n-2)
    int prev = 1;      // F(n-1)
    int current;       // F(n)
    for (int i = 2; i <= n; ++i) {
        current = prev + prev_prev;
        prev_prev = prev;
        prev = current;
    }
    return current;
}

// 尾遞歸計(jì)算階乘
unsigned long long factorialTailRecursive(int n, unsigned long long accumulator = 1) {
    if (n == 0) {
        return accumulator;
    }
    // 遞歸調(diào)用是函數(shù)的最后一個操作
    return factorialTailRecursive(n - 1, n * accumulator);
}

#include <iostream>
#include <stack>
using namespace std;
// 二叉樹節(jié)點(diǎn)結(jié)構(gòu)
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 遞歸先序遍歷
void preorderRecursive(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";       // 訪問根節(jié)點(diǎn)
    preorderRecursive(root->left);  // 遍歷左子樹
    preorderRecursive(root->right); // 遍歷右子樹
}
// 迭代先序遍歷
void preorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";   // 訪問根節(jié)點(diǎn)
        // 右子樹先入棧，左子樹后入棧，保證左子樹先訪問
        if (node->right != nullptr) {
            s.push(node->right);
        }
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }
}
int main() {
    // 構(gòu)建一個簡單的二叉樹
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    cout << "遞歸先序遍歷: ";
    preorderRecursive(root);
    cout << endl;
    cout << "迭代先序遍歷: ";
    preorderIterative(root);
    cout << endl;
    // 釋放內(nèi)存（實(shí)際應(yīng)用中應(yīng)編寫完整的銷毀函數(shù)）
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;
    return 0;
}