The Fibonacci sequence begins with 0 and then 1, and every later term is the sum of the two terms just before it. Writing F(n) for the term at position n (counting from 0):
F(0) = 0F(1) = 1F(n) = F(n - 1) + F(n - 2) for every n >= 2Given n, return F(n).
Example 1
Input: n = 6
Output: 8
Each term adds up the two before it: 0, 1, 1, 2, 3, 5, and then 3 + 5 = 8.
Example 2
Input: n = 1
Output: 1
F(1) is one of the two starting terms, so there is nothing to add up.
Example 3
Input: n = 10
Output: 55
The sequence continues 8, 13, 21, 34, and 21 + 34 = 55.
Constraints
0 <= n <= 30Each term needs only the two terms just before it, so start from F(0) and F(1) and build upward instead of recursing down from F(n).
6
8