Leetcode练习(Python)：递归类：面试题10- I. 斐波那契数列：写一个函数，输入 n ，求斐波那契，Fibonacci数列的第 n 项。斐波那契数列的定义如下： F(0 = 0,   F(1 = 1 F(N = F(N - 1 + F(N - 2, 其中 N > 1.

题目：

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

思路：

递归，别忘了取模啊。

程序：

import functools

class Solution:

@functools.lru_cache

def fib(self, n: int) -> int:

if n == 0:

return 0

elif n == 1:

return 1

else:

return (self.fib(n - 1) + self.fib(n - 2)) % 1000000007