Java or Python please

The Fibonacci sequence begins with and as its first and second terms. After these first two elements, each subsequent element is equal to the sum of the previous two elements.

Programmatically:

• fibonacci(0) = 0
• fibonacci(1) = 1
• fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) Given n , return the number in the sequence.

As an example, n. The Fibonacci sequence to n is . With zero-based indexing,

fibonacci(2) = fibonacci(1) + fibonacci(0) fibonacci(3) = fibonacci(2) + fibonacci(1) fibonacci(4) = fibonacci(3) + fibonacci(2) fibonacci(5) = fibonacci(4) + fibonacci(3) fibonacci(6) = fibonacci(5) + fibonacci(4) fibonacci(6) = 5 + 3 = 8

Description Input Format

The input line contains a single integer, . Complete the recursive function in the editor below. It must return the element in the Fibonacci sequence.

fibonacci has the following parameter(s):

n: the integer index of the sequence to return

Input Format

Input Format

The input line contains a single integer, n.

Constraints

Constraints

0 < n <=30

Output Format

Locked stub code in the editor prints the integer value returned by the function.

Sample Input 0

5 

Sample Output 0

5

CODE GIVEN TO WRITE THE ANSWER:

import java.io.*; import java.util.*;

public class Solution {

public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ }