斐波那契数列
斐波那契数列是一种由意大利数学家斐波那契发现的经典数列。该数列的特点是从第三项开始，每一项都等于前两项之和。它的前两项通常定义为 1 或 0 和 1。
公式定义：
第一项 F(1) = 1；
第二项 F(2) = 1；
.....
第 n 项 F(n) = F(n-1) + F(n-2)，其中 n > 2。
因此，斐波那契数列的前几项为：1, 1, 2, 3, 5, 8, 13, 21, 34, ...。斐波那契数列在自然界、艺术和数学中都有广泛的应用，例如兔子繁殖问题、植物生长、黄金分割等，是数学中一种典型的递推数列。
题目要求
实现一个函数，用于计算斐波那契数列的第 n 项。给定一个正整数 n，要求分别使用三种方法（递归、记忆化、迭代）计算并返回斐波那契数列中第 n 项的值：
递归法：按照定义直接递归计算。记忆化递归：在递归中记录已计算的值，避免重复计算。迭代法：使用循环计算，避免递归的栈开销。示例：
输入: n = 5输出: 5 （因为斐波那契数列为 1, 1, 2, 3, 5, …）做题思路
递归法
原理
递归法是按照斐波那契数列的定义公式直接实现的，即
F(n)=F(n−1)+F(n−2)
递归法的核心思想是将一个大的问题分解成两个较小的子问题，再继续递归地分解，直到到达递归终止条件。
实现过程
基准条件：斐波那契数列的第 1 项和第 2 项的值都为 1。因此，当 n <= 2 时，直接返回 1。递归调用：如果 n > 2，则函数递归调用自身来计算 F(n-1) 和 F(n-2)，并将二者相加得到 F(n)。记忆化递归法
原理
记忆化递归是对递归方法的优化。通过在递归过程中记录已计算的斐波那契值，避免重复计算，从而将时间复杂度降低为 O(n)。
实现过程
设置记忆数组：创建一个数组（或向量）memo，用于保存每一项的计算结果。初始时将所有项的值设为 -1，表示还未计算。基准条件：与递归法相同，当 n <= 2 时，直接返回 1。记忆化递归调用：在递归前先检查 memo[n] 是否已经计算过，如果是，则直接返回该值，避免重复计算。如果未计算过，递归调用计算 F(n-1) 和 F(n-2)，并将结果存入 memo[n] 中，以便后续直接使用。返回结果：最终返回 memo[n] 中保存的结果。迭代法（动态规划）
原理
迭代法通过动态规划的思想，将斐波那契数列的计算转换为自底向上的求解。利用两个变量记录前两项的值，逐步累加出第 n 项。与递归相比，迭代法无需栈空间，时间复杂度为 O(n)，空间复杂度为 O(1)。
实现过程
基准条件：如果 n <= 2，直接返回 1。初始化前两项：设置变量 a 和 b 分别代表 F(1) 和 F(2)，即初始值 a = 1, b = 1。迭代计算：从第 3 项开始，通过循环计算每一项的值。每次迭代更新 a 和 b 的值，使 a 保持前一项，b 保持当前项。返回结果：循环结束后，b 即为所求的 F(n)。知识点
递归和迭代：递归求解斐波那契有直接性，但效率低；迭代法性能更优。动态规划思想：通过记忆化减少重复计算，并优化效率。时间复杂度：不同算法的时间复杂度影响巨大。递归 O(2^n)，记忆化递归和迭代 O(n)。示例代码
C 实现
#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; // 程序正常结束 }