LESSON 395 OF 677 · RECURSION

Recursive Fibonacci

Practice O(2ⁿ)

You get a whole number n.

Return F(n), the number at position n in the Fibonacci sequence. Solve it with a recursive function.

Positions count from 0. The first two numbers are fixed: F(0) = 0 and F(1) = 1. Each later number is the sum of the two before it:

F(n) = F(n - 1) + F(n - 2)      when n is 2 or more

So the sequence starts like this:

0, 1, 1, 2, 3, 5, 8, 13, …

Example 1:

Input: n = 6
Output: 8
Explanation: F(6) = F(5) + F(4) = 5 + 3 = 8.

Example 2:

Input: n = 10
Output: 55
Explanation: F(10) = F(9) + F(8) = 34 + 21 = 55.

Example 3:

Input: n = 0
Output: 0
Explanation: F(0) is one of the two fixed values.

Constraints:

Note:

Don't worry about the time and space complexities of your algorithm.

Hints:

Inside the function, we should first check the base case: if n is less than 2, then we should return n.

If n >= 2, since F(n) = F(n - 1) + F(n - 2), we should return the sum of the recursive calls for n - 1 and n - 2.

STEP 1 OF 2

Guided

Ctrl + Enter to check