# Python 斐波那契(fibonacci)(I)

数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子引入了数列0、1、1、2、3、5、8、13、21、34...，称为斐波那契数列（Fibonacci sequence），又称“黄金分割数列”或者“兔子数列”。使用函数递归或非递归的方式都可以方便地计算斐波那契函数：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2）

```python

# TODO(You): 请实现递归计算斐波那契函数

if __name__ == '__main__':
    print(fibonacci(6))
```

请选出下面的 Python 斐波那契实现代码中，<span style="color:red">错误</span> 的选项。

## template

```python
def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)


if __name__ == '__main__':
    print(fibonacci(6))
```

## 答案

```python
def fibonacci_inner(n, r):
    if n == 1 or n == 2:
        return r

    return fibonacci_inner(n-1, fibonacci_inner(n-2, r))


def fibonacci4(n):
    return fibonacci_inner(n, 0)
```

## 选项

### A

```python
def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)
```

### B

```python
def fibonacci(n):
    if n == 1 or n == 2:
        return 1

    r = [1, 1]
    for i in range(2, n):
        r[1],r[0] = r[1]+r[0],r[1]

    return r[1]
```

### C

```python
def fibonacci_inner(n, m, r0, r1):
    if m == n:
        return r1

    return fibonacci_inner(n, m+1, r1, r0+r1)


def fibonacci(n):
    return fibonacci_inner(n, 2, 1, 1)
```

### D

```python
def fibonacci(n):
    from math import pow, sqrt
    return int(1/sqrt(5)*(pow((1+sqrt(5))/2, n)-pow((1-sqrt(5))/2, n)))
```