c++ 斐波那契数列递归 c++斐波那契算法代码-C++-PHP中文网

c++ 斐波那契数列递归 c++斐波那契算法代码

下次还敢

发布： 2025-11-27 12:49:02

原创

685人浏览过

斐波那契数列定义为F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）；简单递归效率低，存在大量重复计算；记忆化递归通过存储已计算值将时间复杂度降为O(n)；迭代法最优，时间O(n)，空间O(1)，适合大数值计算。

c++ 斐波那契数列递归 c++斐波那契算法代码

斐波那契数列是一个经典的递归问题，数列定义为：第0项是0，第1项是1，从第2项开始，每一项都等于前两项之和。即：

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)（当 n ≥ 2）

简单递归实现

最直观的写法是使用递归函数：

#include <iostream>
using namespace std;
<p>int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}</p><p>int main() {
int n = 10;
cout << "F(" << n << ") = " << fibonacci(n) << endl;
return 0;
}</p>

登录后复制

这个版本代码简洁，但效率很低，因为存在大量重复计算。例如计算 F(5) 时，F(3) 会被多次重复调用。

立即学习“C++免费学习笔记（深入）”；

优化方案：记忆化递归

为了避免重复计算，可以用数组记录已经算过的值：

腾讯混元文生视频

腾讯发布的AI视频生成大模型技术

266

查看详情

#include <iostream>
#include <vector>
using namespace std;
<p>int fib_memo(int n, vector<int>& memo) {
if (n <= 1)
return n;
if (memo[n] != -1)
return memo[n];
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
return memo[n];
}</p><p>int fibonacci_memo(int n) {
vector<int> memo(n + 1, -1);
return fib_memo(n, memo);
}</p><p>int main() {
int n = 10;
cout << "F(" << n << ") = " << fibonacci_memo(n) << endl;
return 0;
}</p>

登录后复制

这样每个值只计算一次，时间复杂度降到 O(n)，空间换时间。

更高效的迭代方法（推荐）

虽然题目要求递归，但实际应用中迭代更高效：

#include <iostream>
using namespace std;
<p>int fibonacci_iterative(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; ++i) {
c = a + b;
a = b;
b = c;
}
return b;
}</p><p>int main() {
int n = 10;
cout << "F(" << n << ") = " << fibonacci_iterative(n) << endl;
return 0;
}</p>

登录后复制

时间 O(n)，空间 O(1)，适合大数值计算。

基本上就这些。递归写法容易理解，但要注意性能问题。小数据可用记忆化，大数据建议用迭代。不复杂但容易忽略效率陷阱。

以上就是c++++ 斐波那契数列递归 c++斐波那契算法代码的详细内容，更多请关注php中文网其它相关文章！