如何统计并输出递归与迭代计算斐波那契数的运算次数与耗时

需求说明 #

基于现有完成的斐波那契C++计算代码，扩展两类统计输出能力，完成两种实现方案的性能对比：

• 分别统计递归、迭代计算过程中的核心运算执行总次数
• 分别测量两种实现的纯计算实际耗时，消除IO操作对统计结果的干扰

改造核心注意事项 #

• 把原来嵌在迭代函数里的斐波那契序列打印逻辑彻底剥离：打印是系统IO操作，单次打印耗时远高于整数加法运算，混在计算流程里会让耗时统计完全不准。
• 运算次数的统计口径要统一：
  • 迭代链路：每在循环里完成一次斐波那契数的加法生成，算1次有效运算
  • 递归链路：每进入一次递归函数做一次分支判断，算1次有效运算
• 计时别用系统墙钟时间：用C++标准库<chrono>里的std::chrono::steady_clock采集时间戳，避免系统自动校时、休眠唤醒导致的计时跳变。

改造后可直接运行的参考代码 #

#include <bits/stdc++.h>
#include <chrono>
using namespace std;

// 全局统计变量
long long iter_op_count = 0;
long long recur_op_count = 0;

// 迭代计算核心逻辑：剥离打印动作，嵌入运算计数
int iterative_calc(int n){
    iter_op_count = 0;
    if(n == 0) return 0;
    if(n == 1) return 1;
    int num1 = 0, num2 = 1, num3;
    for(int j = 2; j <= n; j++){
        num3 = num1 + num2;
        iter_op_count++; // 统计每次加法运算次数
        num1 = num2;
        num2 = num3;
    }
    return num2;
}

// 递归计算核心逻辑：嵌入递归调用计数
int recursive_calc(int num){
    recur_op_count++; // 统计每次递归函数调用次数
    if(num <= 1)
        return num;
    return recursive_calc(num-1) + recursive_calc(num-2);
}

int main (){
    int n;
    cout << "Enter a value for n: ";
    cin >> n;

    // 迭代流程计时计算
    auto iter_start = chrono::steady_clock::now();
    int iter_result = iterative_calc(n);
    auto iter_end = chrono::steady_clock::now();
    auto iter_cost = chrono::duration_cast<chrono::nanoseconds>(iter_end - iter_start).count();

    // 迭代结果输出（放在计时停止后，不干扰统计）
    printf("\n迭代计算结果: %d\n", iter_result);
    printf("迭代运算执行次数: %lld\n", iter_op_count);
    printf("迭代计算耗时: %.3f 微秒\n", iter_cost / 1000.0);

    // 递归流程计时计算
    recur_op_count = 0;
    auto recur_start = chrono::steady_clock::now();
    int recur_result = recursive_calc(n);
    auto recur_end = chrono::steady_clock::now();
    auto recur_cost = chrono::duration_cast<chrono::nanoseconds>(recur_end - recur_start).count();

    // 递归结果输出
    printf("\n递归计算结果: %d\n", recur_result);
    printf("递归运算执行次数: %lld\n", recur_op_count);
    printf("递归计算耗时: %.3f 微秒\n", recur_cost / 1000.0);

    getchar();
    return 0;
}

典型性能观测规律 #

当n取值较大（如n=40）时，两种实现的差异会非常直观：

• 迭代实现的运算次数与n呈线性正相关，运算耗时随n增长无指数级抬升，全程几乎无感知延迟
• 无记忆化优化的原生递归实现，运算次数随n增大呈2^n级别的指数增长，n=40时运算总次数已经突破2亿次，耗时会达到秒级，远慢于迭代实现

内容的提问来源于stack exchange，提问作者Tenzin p