Question

This is an intro to Java question. Please solve using pseudocode if you can.

Fibonacci ​ In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Hence, a Fibonacci number ​n ​ may be found with ​f(n) = f(n-1) + f(n-2).
Write a simple program that finds the the Fibonacci number at a specified position in the Fibonacci series.

Facts

● Each number in Fibonacci is the sum of the previous two numbers in sequence.

● FIbonacci of 0 equals 0, i.e. ​f(0) = 0

● The starting two values in the series for this formula may be considered as 0 and 1

● In order to find a specific Fibonacci number, you must first find all of its preceding fibonacci numbers using the formula above.

Input The first input is the number of test cases. Each additional input is a non-negative integer and represents the specified index into the Fibonacci sequence.

Output Print the value at that position in the Fibonacci series.


Sample Input

4

1

2

4

20

Sample Output

1

1

3

6765

Answer 1

import java.util.Scanner;

public class Fibonacci {

    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            System.out.println(fibonacci(in.nextInt()));
        }
    }
}