徐静远  (讲师)

Fibonacci数的C++实现方法对比（递归与线性表）

点击次数：

最近在备课《数据结构与算法》时，多次以Fibonacci数作为例子，本博客以C++实现的例子，做一下讨论。

作为典型的递归问题，算法可以利用递归的方式来实现。

int Fib(int n)
{
if (n <= 2)
    return 1;
return Fib(n - 1) + Fib(n - 2);
}

可以看出来这样的实现方式虽然简单，但是存在大量的重复计算，比如计算Fib(n-1)的过程中还是要重新计算Fib(n-2)，而这些是可以避免的。我们可以借助数据结构中栈的思想，利用vector来依次保存Fibonacci数，从而减少循环次数：

int Fibv(int n){

if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 1;
std::vector<int> v = {1, 1};
int next = 0;
for (int i = 2; i < n; ++i)
{
    next = v[i - 1] + v[i - 2];
    v.push_back(next);
}
return v.back();
}

通过栈实现了上述计算以后，可以看出来，循环次数一下就减少到了O(N)，我们可以通过程序运行时间来对比一下两个算法：

#include<iostream>
#include<vector>
#include<algorithm>
#include <chrono>
int main()
{
int n = 50;
auto start = std::chrono::high_resolution_clock::now();
std::cout << Fib(n) << std::endl;
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Recursion Run time: " << duration.count() << " micro second." << std::endl;

std::cout << Fibv(n) << std::endl;
auto end2 = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - end);
std::cout << "Vector Run time: " << duration2.count() << " micro second." << std::endl;

return 0;
}

我们发现两个算法的计算时间会相差非常大！

可以看出来基于回归的算法计算时间在指数的增长，这对于算法设计是十分不利的！

算法改用了Vector以后，时间上大幅度的节约了，空间复杂度却来到了O(N)，但这其实也是可以继续优化的，因为我们不需要一直保存所有的数据来计算，只需要前两个就行，因此我们可以用队列“先进先出的”思想来移除前期的Fibonacci数，这个改进方案的C++实现就留给大家吧～

15:41:05  2025-10-20