81、无穷数列1、1、2、3、5、8、13、21、34、55••••• 称为 Fibonacci 数列（方法可使用任意一种计算程序。设计或语言或者伪代码进行描述） 1、试给出数列的递归定义 2、用程序实现递归算法来计算数列中第n个数值 3、用程序实现非递归算法计算数列第n个元素值

Fibonacci 数列是一个非常著名的数列，它的每个数字是前两个数字之和。这个序列通常由1, 1开始，并以这种方式继续生成新的数字：

1. **递归定义**：
- 当 n = 0 或 n = 1 时，F(n) = n （基础情况）
- 对于 n > 1，F(n) = F(n-1) + F(n-2) （递归关系）

2. **递归算法（Python）**：

def fibonacci_recursive(n):
    if n <= 0:
        return "Invalid input"
    elif n == 1 or n == 2:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

这个函数会反复调用自身，直到达到基本情况。

3. **非递归算法（动态规划）**：

def fibonacci_non_recursive(n):
    fib_sequence = [0, 1] + [0] * (n - 1)
    for i in range(2, n+1):
        fib_sequence[i] = fib_sequence[i-1] + fib_sequence[i-2]
    return fib_sequence[n]

# 如果需要得到第n个元素，直接调用此函数即可
fib_n = fibonacci_non_recursive(n)

这个算法避免了递归带来的重复计算，通过列表存储已经计算过的项来提高效率。