编程题：斐波那契数列（递归）
利用递归的方法给出斐波那契数列的前n项。
**提示：**
仔细观察递归公式：
$$f_{n} = f_{n-1} + f_{n-2}$$
$$f_{n-1} = f_{n-2} + f_{n-3}$$
从上面的表达式可以看出$$f_{n-2}$$在求$$f_{n}$$和$$f_{n-1}$$的时候会递归计算两次，这会造成计算速度较慢的问题，考虑针对这个进行优化。
请注意算法的优化，递归的方法若在递归层次较深的情况下，运行时间较长，思考如何提高递归的效率
### 输入格式:
一行输入斐波那契数列的项数n
### 输出格式:
以列表的形式输出斐波那契数列的前n项
### 输入样例:
在这里给出一组输入。例如：
in
5
### 输出样例:
在这里给出相应的输出。例如：
out
[1, 1, 2, 3, 5]
### 输入样例:
在这里给出一组输入。例如：
in
40
### 输出样例:
在这里给出相应的输出。例如：
out
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155]
answer：若无答案欢迎评论
**提示：**
仔细观察递归公式：
$$f_{n} = f_{n-1} + f_{n-2}$$
$$f_{n-1} = f_{n-2} + f_{n-3}$$
从上面的表达式可以看出$$f_{n-2}$$在求$$f_{n}$$和$$f_{n-1}$$的时候会递归计算两次，这会造成计算速度较慢的问题，考虑针对这个进行优化。
请注意算法的优化，递归的方法若在递归层次较深的情况下，运行时间较长，思考如何提高递归的效率
### 输入格式:
一行输入斐波那契数列的项数n
### 输出格式:
以列表的形式输出斐波那契数列的前n项
### 输入样例:
在这里给出一组输入。例如：
in
5
### 输出样例:
在这里给出相应的输出。例如：
out
[1, 1, 2, 3, 5]
### 输入样例:
在这里给出一组输入。例如：
in
40
### 输出样例:
在这里给出相应的输出。例如：
out
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155]
answer：若无答案欢迎评论
