算法设计与分析（斐波那契数列

目录

• 斐波那契数列的递归实现

• 斐波那契数列的定义
• 递归实现
• 注意事项

• 小结：

斐波那契数列的递归实现

在编程中，斐波那契数列是一个非常著名的序列，它通常定义为每个数字（从第3个数字开始）都是前两个数字的和，且前两个数字分别是0和1。

斐波那契数列的定义

在本实现中，斐波那契数列的定义略有不同，具体为：

• 当 n == 0 时，返回 1。
• 当 n == 1 时，也返回 1。
• 从 n == 2 开始，每个数都是前两个数的和。

递归实现

下面是使用递归方法实现这个非标准斐波那契数列的C++代码：

#include<iostream>  
  
using namespace std;  
  
int fibonacci(int n){  
	// 边界条件  
	if (n == 0){  
		return 1;  
	}  
	else if (n == 1){  
		return 1;  
	}  
	  
	// 递归调用  
	return fibonacci(n-2) + fibonacci(n-1);  
}  
  
int main() {  
	cout << "斐波那契数列的第3个数是: " << fibonacci(3) << endl;  
	return 0;  
}

注意事项

效率问题：递归实现虽然简洁，但对于较大的 n 值，其效率非常低，因为它会重复计算很多子问题。对于实际应用，建议使用迭代方法或带有备忘录的递归方法（也称为动态规划）来提高效率。

非标准定义：本实现中的斐波那契数列定义与标准定义不同，因此在与其他斐波那契数列相关的算法或问题时，需要特别注意这一点。

边界条件：由于起始条件的不同，这个实现产生的数列将是一个非标准的斐波那契数列。