RecursiveFibonacci

package Uprajneniq;

import java.util.ArrayDeque;
import java.util.Scanner;

public class RecursiveFibonacci {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);


        ArrayDeque<Long> Fibonacci = new ArrayDeque<>(); // Create a deque to store Fibonacci numbers

        // Read the input: the nth Fibonacci number to calculate
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();

        // Call the getFibonacci method to calculate the nth Fibonacci number and print the result
        System.out.println(getFibonacci(Fibonacci, N));
    }

    // Method to calculate the nth Fibonacci number using recursion
    private static Long getFibonacci(ArrayDeque<Long> Fibonacci, int N) {
        if (N < 2) {
            return 1L; // Base case: if N is 0 or 1, return 1
        } else {
            // Initialize the first two Fibonacci numbers
            Fibonacci.offer(0L);
            Fibonacci.offer(1L);

            // Generate the Fibonacci sequence up to N
            for (int i = 0; i < N; i++) {
                long Sum = Fibonacci.poll() + Fibonacci.peek(); // Calculate the sum of the last two Fibonacci numbers
                Fibonacci.offer(Sum); // Add the sum to the sequence
            }
        }

        Fibonacci.poll(); // Remove the first element (0) as it's not part of the Fibonacci sequence
        return Fibonacci.peek(); // Return the nth Fibonacci number
    }
}