递归 vs 迭代

C++ 递归迭代

数据结构与算法

发布日期: 2022-08-24

更新日期: 2022-09-21

文章字数: 615

阅读时长: 2 分

首先提出两个问题

所有递归都可以改写成循环吗？
改写后会有什么好处？

接下来我们仔细分析下具体的区别

递归转换为迭代的方法

对于递归而言有两种转换方式

一、直接转换法

方法：使用变量保存中间结果

计算阶乘：

long fact(int n) {
　　if (n==0) return 1;
　　else return n*fact(n-1);
}

long fact(int n) {
　　int res = 1;
　　for (int i=1; i<=n;i++)
　      res *= i;
　　return res;
}

可以看到，时间复杂度依旧为 \(\mathcal{O}(n)\)，但空间复杂度已经从 \(\mathcal{O}(n) \to \mathcal{O}(1)\) 了，因为原本需要调用 fact(...) \(n\) 次，但现在只需要 \(1\) 次了

二、间接转换法

方法：使用栈保存中间结果

树的先序遍历：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void travel(TreeNode *root)
    {
        if(root == nullptr)
        {
            return;
        }
        res.push_back(root->val);
        travel(root->left);
        travel(root->right);
    }
    vector<int> preorderTraversal(TreeNode* root) 
    {
        travel(root);
        return res;
    }
private:
    vector<int> res;
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode *p=root;
        while (!st.empty() || p) {
            while (p) {
                ans.emplace_back(p->val);
                st.emplace(p);
                p = p->left;
            }
            p = st.top();
            st.pop();
            p = p->right;
        }
        return ans;
    }
};