递推、递归和迭代都是解决问题的方法，它们之间有一定的联系。递推和迭代可以用于实现递推关系，但它们也有各自独立的应用场景。
递推：递推是一种通过重复计算较小的相似子问题来解决较大问题的方法。递推的关键思想是将原问题分解为一系列较小的相似子问题，然后通过计算子问题的解来得到原问题的解。
递归：递归是一种函数调用自身的技术，通过将问题分解成相似的子问题来解决问题。在递归实现中，函数在其定义中调用自身，这样可以通过重复调用函数来解决问题。递归可以用于实现递推关系。
迭代：迭代是一种重复执行某些操作的方法，通过在每个迭代中更新变量来逐步解决问题。迭代可以用于实现递推关系。许多人说的递推算法，实际指迭代算法。
以下是一些使用递归函数的例子：
1. 计算了1到n的整数之和。
```cpp
#include
using namespace std;
int sum(int n) {
if (n == 1) {
return 1;
} else {
return n + sum(n - 1);
}
}
int main() {
int n = 5;
cout << "Sum of integers from 1 to " << n << " is: " << sum(n) << endl;
return 0;
}
```
2. 计算斐波那契数列的第n项。
```python
def fibonacci(n):
return "Invalid input"
elif n == 1:
return [0]
elif n == 2:
return [0, 1]
else:
fib_seq = [0, 1]
for i in range(2, n):
fib_seq.append(fib_seq[i-1] + fib_seq[i-2])
return fib_seq[n-1]
```
```cpp
#include
using namespace std;
int recursiveSum(int n) {
if (n == 0) { // 终止条件
return 0;
} else {
return n + recursiveSum(n - 1); // 递归调用
}
}
int main() {
int n;
cout << "请输入一个正整数： ";
cin >> n;
int sum = recursiveSum(n); // 调用递归函数计算和
cout << "从1到" << n << "的所有整数的和为： " << sum << endl;
return 0;
}
```
以下是重构后的代码：
```cpp
#include
using namespace std;
// 迭代算法用Python实现
int iterativeSum(int n) {
int result = 0;
while (n > 0) {
result += n;
n--;
}
return result;
}
int main() {
int n;
cout << "请输入一个正整数： ";
cin >> n;
int sum = iterativeSum(n); // 调用递归函数计算和
cout << "从1到" << n << "的所有整数的和为： " << sum << endl;
return 0;
}
```
在这个例子中，factorial(n)函数通过递归调用自身来计算n的阶乘。基本情况是n == 0,此时函数返回1。在递归情况下，函数返回n * factorial(n - 1),这是n的阶乘的定义。
★迭代算法用C++实现(关键代码):
```cpp
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
```
★迭代算法用Python实现(关键代码):
```python
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
```
3. 计算斐波那契数列
斐波那契数列(Fibonacci Sequence):
斐波那契数列是指从 0 和 1 开始，后面的每一项都是前两项之和。也就是说，第 n 个斐波那契数等于第 n-1 个斐波那契数与第 n-2 个斐波那契数的和。斐波那契数列的前几项依次为：0, 1, 1, 2, 3, 5, 8, 13, 21, ...。可以使用递归或迭代的方式来生成斐波那契数列。
★递归算法用C++实现(关键代码):
```cpp
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
```
在这个例子中，fibonacci(n)函数通过递归调用自身来计算斐波那契数列的第n项。基本情况是n <= 1,此时函数返回n。在递归情况下，函数返回fibonacci(n - 1) + fibonacci(n - 2),这是斐波那契数列的定义。
以下是重构后的代码：
```python
def fibonacci(n):
if n <= 0:
return n
else:
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
```
