【python练习】python斐波那契数列超时问题

计算斐波那契数列第n项的数字
Description计算斐波那契数列第n项的数字，其中f(1)=f(2)=1,f(n)=f(n-1)+f(n-2)，如1，1，2，3，5,......Input
正整数n(n<100)Output
一个整数f(n)Sample Input 1 8
Sample Output 121
Source中学生可以这样学Python，P187例8-19

一、使用递归，出现超时

n=int(input())
def f(n):if n==1 or n==2:return 1else:return f(n-1)+f(n-2)
print(f(n))

二、使用列表，通过

n=int(input())
a=[1,1]
if n==1 or n==2:print(1)
else:for i in range(2,n):a.append(a[i-2]+a[i-1])
print(a[n-1])