690. Nth Fibonacci Number

Given a non-negative integer N, return the Nth Fibonacci number using recursion. The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2) for N >= 2. The sequence starts: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Input: A single non-negative integer N (0 ≤ N ≤ 88).

Output: A single integer — the Nth Fibonacci number.

Examples

Input: 0
Output: 0
Explanation: F(0) = 0 by definition (base case).

Input: 1
Output: 1
Explanation: F(1) = 1 by definition (base case).

Input: 10
Output: 55
Explanation: F(10) = F(9)+F(8) = 34+21 = 55. Sequence: 0,1,1,2,3,5,8,13,21,34,55.

Constraints

• 0 <= N <= 78

Asked by