递归 是什么?请用C++代码实现
时间: 2023-10-06 15:05:17 浏览: 42
递归是函数直接或间接调用自身的一种算法或编程技巧。它可以用来解决许多问题,如计算阶乘、斐波那契数列等。
下面是一个使用递归计算阶乘的C++代码:
```c++
#include <iostream>
using namespace std;
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
int n = 5;
cout << n << "! = " << factorial(n) << endl;
return 0;
}
```
在上面的代码中,`factorial`函数使用递归计算阶乘。当`n`等于0时,`factorial`函数返回1,否则它返回`n`和`factorial(n - 1)`的乘积。在`main`函数中,我们调用`factorial`函数来计算5的阶乘。
相关问题
什么递归&迭代 并且请分别用C++代码说明
递归和迭代都是计算机科学中常用的算法设计和实现方法。
递归是指一个函数在执行过程中调用了自身。递归算法往往能够简化问题的表达和解决,但也可能导致栈溢出等问题。下面是一个用C++实现的递归函数,计算斐波那契数列的第n项:
```cpp
int fibonacci(int n) {
if (n == 0 || n == 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
```
迭代是指通过循环来重复执行一段代码,以达到解决问题的目的。迭代算法往往需要使用循环变量等额外的变量来控制循环的次数和状态。下面是一个用C++实现的迭代函数,计算斐波那契数列的第n项:
```cpp
int fibonacci(int n) {
if (n == 0 || n == 1) {
return n;
}
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int sum = a + b;
a = b;
b = sum;
}
return b;
}
```
两种方法各有优缺点,具体实现方法要根据问题的复杂程度和算法的效率来选择。
生成递归实现二叉树层次遍历的c++代码
好的,下面是一份使用递归实现二叉树层次遍历的 C++ 代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void levelOrder(TreeNode* root, int level, vector<vector<int>>& res) {
if (!root) return;
if (level >= res.size()) {
res.push_back(vector<int>());
}
res[level].push_back(root->val);
levelOrder(root->left, level + 1, res);
levelOrder(root->right, level + 1, res);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
levelOrder(root, 0, res);
return res;
}
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
vector<vector<int>> res = levelOrder(root);
for (vector<int> level : res) {
for (int val : level) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
```
这段代码首先定义了一个 TreeNode 结构体来表示二叉树的节点。然后定义了一个 levelOrder 函数,使用递归来实现层次遍历,并将结果存入一个二维数组 res 中。最后在 main 函数中创建一个二叉树,并输出遍历结果。
需要注意的是,这个代码中的 levelOrder 函数使用了一个辅助参数 level 来表示当前遍历的层数,以及一个二维数组 res 来存储遍历结果。由于递归过程中需要对 res 进行修改,因此这里使用了引用传递。