递归和非递归分别实现求第n个斐波那契数

### 回答1：
递归实现求第n个斐波那契数：

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

非递归实现求第n个斐波那契数：

def fibonacci_iterative(n):
    if n <= 1:
        return n
    else:
        a, b = , 1
        for i in range(2, n+1):
            c = a + b
            a, b = b, c
        return b

### 回答2：
斐波那契数列（Fibonacci sequence）是指这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)(n>=2，n∈N*)。

递归实现求第n个斐波那契数的过程：

1.在递归函数中先写出递归终止条件：

if n == 0:
return 0
elif n == 1:
return 1

2. 再写出递归函数的递推公式：

return fibonacci(n-1) + fibonacci(n-2)

3. 最后调用递归函数输出结果：

print(fibonacci(n))

递归实现虽然简单易懂，但是存在大量重复计算，效率较低。

非递归实现求斐波那契数的过程：

1.初始化a，b两个变量为0和1；

a, b = 0, 1

2.使用for循环将a和b一直循环到第n个斐波那契数；

for i in range(n):
a, b = b, a + b

3.返回a即为第n个斐波那契数：

return a

非递归实现求斐波那契数比递归更加高效，因为没有重复计算。

### 回答3：
斐波那契数列是指数列中每个数都是前两个数之和的数列。斐波那契数列的前几项是：0、1、1、2、3、5、8、13、21、34、55、89、…

递归实现求第n个斐波那契数：

递归就是一种调用自身的函数，因为斐波那契数列是由前两个数的和得到的，所以递归计算第n个斐波那契数的方法就是分别递归计算前面两个斐波那契数的和，直到求得第n个斐波那契数为止。

实现代码如下：

def fibonacci_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

非递归实现求第n个斐波那契数：

非递归就是使用循环来实现计算的过程，因为斐波那契数列是由前两个数的和得到的，所以计算第n个斐波那契数时需要使用循环，依次累加前面两个数的和，直到求得第n个斐波那契数为止。

实现代码如下：

def fibonacci_iterative(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a = 0
        b = 1
        for i in range(2, n+1):
            c = a + b
            a = b
            b = c
        return b

两种方法的优缺点：

递归的实现方法简单，易于理解，但是当n比较大时，递归调用的层数会越来越多，导致栈溢出或者消耗过多的内存。

非递归的实现方法比较复杂，但是可以避免出现栈溢出或者消耗过多内存的情况，因此在处理大量数据时更为有效。