递推和递归的区别c++

递推和递归都是解决问题的方法，但它们的实现方式不同。递推是通过已知的初始值和递推公式，依次推算出后续的值，直到得到最终的结果。而递归则是通过将问题分解成更小的子问题，并不断递归调用自身来解决问题。递推通常使用循环结构来实现，而递归则使用函数调用来实现。

相关问题

递归C++Pell数列

Pell数列是指满足递推式P(n+1) = 2P(n) + P(n-1)，且P(0) = 0，P(1) = 1的数列。下面是一个递归实现Pell数列的C代码：

#include <stdio.h>

int Pell(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return 2 * Pell(n-1) + Pell(n-2);
    }
}

int main() {
    int n;
    printf("请输入Pell数列的项数：");
    scanf("%d", &n);
    printf("Pell数列的前%d项为：\n", n);
    for (int i = 0; i < n; i++) {
        printf("%d ", Pell(i));
    }
    printf("\n");
    return 0;
}

这段代码中，递归函数Pell(n)的实现与递推式一致。当n为0或1时，直接返回P(0)和P(1)的值。当n大于1时，根据递推式计算P(n)的值。

在主函数中，首先读入需要计算的Pell数列的项数，然后逐一计算每一项的值并输出。

需要注意的是，递归实现虽然简单易懂，但在计算大量项时效率较低，因为存在大量的重复计算。为了提高效率，可以使用迭代方法或记忆化搜索等技巧。

遍历二叉树c++递推

以下是C++中二叉树的三种遍历方式的递归实现和非递归实现：

1. 先序遍历

递归实现：

void preorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

非递归实现：

void preorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right != nullptr) {
            s.push(node->right);
        }
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }
}

2. 中序遍历

递归实现：

void inorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

非递归实现：

void inorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node != nullptr || !s.empty()) {
        while (node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

3. 后序遍历

递归实现：

void postorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

非递归实现：

void postorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* node = root;
    TreeNode* last = nullptr;
    while (node != nullptr || !s.empty()) {
        while (node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        if (node->right == nullptr || node->right == last) {
            cout << node->val << " ";
            s.pop();
            last = node;
            node = nullptr;
        } else {
            node = node->right;
        }
    }
}
--相关问题--: