斐波那契数列定义为F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）；简单递归效率低，存在大量重复计算；记忆化递归通过存储已计算值将时间复杂度降为O(n)；迭代法最优，时间O(n)，空间O(1)，适合大数值计算。
斐波那契数列是一个经典的递归问题，数列定义为：第0项是0，第1项是1，从第2项开始，每一项都等于前两项之和。即：
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)（当 n ≥ 2）
简单递归实现
最直观的写法是使用递归函数：
#include using namespace std;int fibonacci(int n) {if (n <= 1)return n;return fibonacci(n - 1) + fibonacci(n - 2);}
int main() {int n = 10;cout << "F(" << n << ") = " << fibonacci(n) << endl;return 0;}
这个版本代码简洁，但效率很低，因为存在大量重复计算。例如计算 F(5) 时，F(3) 会被多次重复调用。
立即学习“C++免费学习笔记（深入）”；
优化方案：记忆化递归
为了避免重复计算，可以用数组记录已经算过的值：
#include #include using namespace std;int fib_memo(int n, vector& 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];}
int fibonacci_memo(int n) {vector memo(n + 1, -1);return fib_memo(n, memo);}
int main() {int n = 10;cout << "F(" << n << ") = " << fibonacci_memo(n) << endl;return 0;}
这样每个值只计算一次，时间复杂度降到 O(n)，空间换时间。
更高效的迭代方法（推荐）
虽然题目要求递归，但实际应用中迭代更高效：
#include using namespace std;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;}
int main() {int n = 10;cout << "F(" << n << ") = " << fibonacci_iterative(n) << endl;return 0;}
时间 O(n)，空间 O(1)，适合大数值计算。
基本上就这些。递归写法容易理解，但要注意性能问题。小数据可用记忆化，大数据建议用迭代。不复杂但容易忽略效率陷阱。
以上就是c++++ 斐波那契数列递归 c++斐波那契算法代码的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486455.html
微信扫一扫 
支付宝扫一扫 
