C/C++ 每日一练：计算斐波那契数列的第 n 项（递归、记忆化、迭代）

#include <stdio.h>  

// 方法一：递归法计算斐波那契数列的第 n 项  
// 定义一个递归函数，接收一个整数 n 作为参数，返回斐波那契数列的第 n 项  
int fibonacci_recursive(int n) {
    if (n <= 2) {      // 如果 n 小于或等于 2，根据斐波那契数列的定义，返回 1  
        return 1;
    }
    // 否则，返回前两个斐波那契数的和，即递归调用自身计算 F(n-1) 和 F(n-2)  
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);  // F(n) = F(n-1) + F(n-2)  
}

// 方法二：记忆化递归法计算斐波那契数列的第 n 项  
// 定义一个记忆化递归函数，接收一个整数 n 和一个数组 memo 作为参数，返回斐波那契数列的第 n 项  
int fibonacci_memoization(int n, int memo[]) {
    if (n <= 2) {        // 如果 n 小于或等于 2，根据斐波那契数列的定义，返回 1  
        return 1;
    }
    // 如果 memo 数组中对应 n 的值已经被计算过（即不为 -1），则直接返回该值  
    if (memo[n] != -1) {
        return memo[n];
    }
    // 否则，递归计算 F(n-1) 和 F(n-2) 的和，并将结果存储在 memo 数组中，然后返回该结果  
    memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo); // 递归并存储结果  
    return memo[n];
}

// 方法三：迭代法计算斐波那契数列的第 n 项  
// 定义一个迭代函数，接收一个整数 n 作为参数，返回斐波那契数列的第 n 项  
int fibonacci_iterative(int n) {
    if (n <= 2) {      // 如果 n 小于或等于 2，根据斐波那契数列的定义，返回 1  
        return 1;
    }
    int a = 1, b = 1;  // 初始化两个变量 a 和 b，分别代表斐波那契数列的前两项 F(1) 和 F(2)  
    int result = 0;    // 初始化结果变量 result  

    // 从第三项开始迭代计算斐波那契数列  
    for (int i = 3; i <= n; i++) {
        result = a + b;             // 当前项等于前两项之和  
        a = b;                      // 更新 a 为前一项的值（即 F(n-2) 更新为 F(n-1)）  
        b = result;                 // 更新 b 为当前项的值（即 F(n-1) 更新为 F(n)）  
    }
    return result;  // 返回第 n 项的值  
}

int main() 
{
    int n = 5;  // 设定要计算的斐波那契数列的项数  

    // 使用递归法计算并打印斐波那契数列的第 n 项  
    printf("递归法：斐波那契数列的第 %d 项是 %d\n", n, fibonacci_recursive(n));

    // 使用记忆化递归法计算并打印斐波那契数列的第 n 项  
    // 首先初始化一个大小为 100 的数组 memo，用于存储已经计算过的斐波那契数  
    int memo[100];
    for (int i = 0; i < 100; i++) memo[i] = -1;  // 将 memo 数组的所有元素初始化为 -1，表示未计算  
    printf("记忆化递归法：斐波那契数列的第 %d 项是 %d\n", n, fibonacci_memoization(n, memo));

    // 使用迭代法计算并打印斐波那契数列的第 n 项  
    printf("迭代法：斐波那契数列的第 %d 项是 %d\n", n, fibonacci_iterative(n));

    return 0;  // 程序正常结束  
}

C++实现

#include <iostream>  // 引入输入输出流库，用于输入输出操作  
#include <vector>    // 引入向量库，用于存储动态数组  
using namespace std; // 使用标准命名空间，避免每次调用标准库时都需要加std::前缀  

// 方法一：递归法计算斐波那契数列的第 n 项  
int fibonacci_recursive(int n) {
    if (n <= 2) {      // 基础条件：如果n小于或等于2，则返回1，因为斐波那契数列的前两项都是1  
        return 1;
    }
    // 递归调用自身计算斐波那契数列的第n-1项和第n-2项的和  
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);  // F(n) = F(n-1) + F(n-2)  
}

// 方法二：记忆化递归法计算斐波那契数列的第 n 项  
int fibonacci_memoization(int n, vector<int>& memo) {
    if (n <= 2) {         // 基础条件：如果n小于或等于2，则返回1  
        return 1;
    }
    // 如果memo数组中对应n的值已经被计算过（即不为-1），则直接返回该值  
    if (memo[n] != -1) {
        return memo[n];
    }
    // 否则，递归计算第n-1项和第n-2项的和，并将结果存储在memo数组中，然后返回该结果  
    memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo); // 递归并存储结果  
    return memo[n];
}

// 方法三：迭代法计算斐波那契数列的第 n 项  
int fibonacci_iterative(int n) {
    if (n <= 2) {         // 如果n小于或等于2，则直接返回1  
        return 1;
    }

    int a = 1, b = 1;     // 初始化两个变量a和b，分别代表斐波那契数列的前两项F(1)和F(2)  
    int result = 0;       // 初始化结果变量result，用于存储当前计算的斐波那契数  

    // 从第三项开始迭代计算斐波那契数列  
    for (int i = 3; i <= n; i++) {
        result = a + b;              // 当前项等于前两项之和  
        a = b;                       // 更新a为前一项的值（即F(n-2)更新为F(n-1)）  
        b = result;                  // 更新b为当前项的值（即F(n-1)更新为F(n)）  
    }
    return result; // 返回第n项的值  
}

int main() 
{
    int n = 5; // 设定要计算的斐波那契数列的项数  

    // 使用递归法计算并打印斐波那契数列的第n项  
    cout << "递归法：斐波那契数列的第 " << n << " 项是 " << fibonacci_recursive(n) << endl;

    // 使用记忆化递归法计算并打印斐波那契数列的第n项  
    // 首先初始化一个大小为n+1的memo数组，并将所有元素初始化为-1，表示未计算  
    vector<int> memo(n + 1, -1);
    cout << "记忆化递归法：斐波那契数列的第 " << n << " 项是 " << fibonacci_memoization(n, memo) << endl;

    // 使用迭代法计算并打印斐波那契数列的第n项  
    cout << "迭代法：斐波那契数列的第 " << n << " 项是 " << fibonacci_iterative(n) << endl;

    return 0; // 程序正常结束  
}