Foundations Recursion basics
41. Fibonacci Number
Easy 147 DSA Sheet
The Fibonacci sequence starts with 0 and 1, and every later term is the sum of the two terms just before it: 0, 1, 1, 2, 3, 5, 8, 13, and so on.
F(n) is the term at index n, counting from 0:
- F(0) = 0
- F(1) = 1
- F(2) = F(1) + F(0) = 1 + 0 = 1
- F(3) = F(2) + F(1) = 1 + 1 = 2
- F(4) = F(3) + F(2) = 2 + 1 = 3
Given an integer n, return F(n).
Example 1
Input: n = 7
Output:
13Explanation: The terms at indexes 0 to 7 are 0, 1, 1, 2, 3, 5, 8 and 13. The last one, 13, is 5 + 8.
Example 2
Input: n = 0
Output:
0Explanation: The sequence starts at index 0, and its first term is 0.
Example 3
Input: n = 60
Output:
1548008755920Check your understanding
Work out the answer for this input before you write any code.
n = 9
Constraints
0 ≤ n ≤ 90
Clarifying questions
What you would ask an interviewer before writing any code.