斐波那契数列以意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci）的名字命名，他在《算盘书》中首次引入了这个数列。该数列从0和1开始，后续的元素都是前两个元素的和，即：
\[ F(n) = F(n-1) + F(n-2) \]
斐波那契数列的前几个数字是：0, 1, 1, 2, 3, 5, 8, 13, 21, ...
### 递推公式
斐波那契数列的递推公式如上所示，即第 n 个斐波那契数等于第 n-1 和第 n-2 个斐波那契数的和。这个公式可以用递归的方式实现，也可以用循环迭代的方式实现。
### 递归实现
递归是一种将问题分解为更小的子问题来解决的方法。在斐波那契数列中，递归的思想是将问题分解为计算第 n-1 和第 n-2 个斐波那契数的问题，直到递归到基本情况（n=0 或 n=1）为止。
```java public static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); } ```
### 循环迭代实现
循环迭代是另一种实现斐波那契数列的方法，它通过迭代计算每个斐波那契数，从而避免了递归中的重复计算。
```java public static int fibonacci(int n) { if (n <= 1) { return n; } int prev = 0, curr = 1; for (int i = 2; i <= n; i++) { int next = prev + curr; prev = curr; curr = next; } return curr; } ```
### 性能分析
递归实现的斐波那契数列在计算较大的斐波那契数时性能较差，因为它会重复计算相同的子问题。循环迭代实现则更为高效，因为它避免了重复计算，只需计算每个斐波那契数一次。
总体来说，斐波那契数列是一个很好的算法问题，可以帮助理解递归、循环和动态规划等算法思想。
### C 语言
```c #include <stdio.h> int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); } int main() { int n = 10; for (int i = 0; i < n; i++) { printf("%d ", fibonacci(i)); } return 0; } ```
### C++ 语言
```cpp #include <iostream> int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); } int main() { int n = 10; for (int i = 0; i < n; i++) { std::cout << fibonacci(i) << " "; } return 0; } ```
### Java 语言
```java public class Fibonacci { public static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); } public static void main(String[] args) { int n = 10; for (int i = 0; i < n; i++) { System.out.print(fibonacci(i) + " "); } } } ```
### Python 语言
```python def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2) n = 10 for i in range(n): print(fibonacci(i), end=" ") ```
### Go 语言
```go package main import "fmt" func fibonacci(n int) int { if n <= 1 { return n } return fibonacci(n-1) + fibonacci(n-2) } func main() { n := 10 for i := 0; i < n; i++ { fmt.Print(fibonacci(i), " ") } } ```
### PHP 语言
```php <?php function fibonacci($n) { if ($n <= 1) { return $n; } return fibonacci($n - 1) + fibonacci($n - 2); } $n = 10; for ($i = 0; $i < $n; $i++) { echo fibonacci($i) . " "; } ?> ```
