Fibonacci Number

Easy~10 min

Given a non-negative integer n, return the nth Fibonacci number.

The Fibonacci sequence is defined as:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) for n >= 2

You must solve this problem recursively.

For example, fibonacci(10) returns 55.

Examples

Example 1
Input: n = 0
Output: 0
Explanation: F(0) = 0 by definition.
Example 2
Input: n = 1
Output: 1
Explanation: F(1) = 1 by definition.
Example 3
Input: n = 10
Output: 55
Explanation: The sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Constraints

  • 0 <= n <= 30
  • You must use recursion.
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run