Recursive Fibonacci

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {
    private static long[] memory;//тук си пазим вече преизчислените ст-ти

    public static void main(String[] args) throws IOException {
        // Scanner scanner = new Scanner(System.in);


        var reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        memory = new long[n + 1];

        long result = getFibonacci(n); //тук си разписваме метод, по който получаваме резултата
        System.out.println(result);
    }

    private static long getFibonacci(int n) {
        if (n < 2) {
            return 1;
        }
        if (memory[n] != 0) {
            return memory[n];
        }
        return memory[n] = getFibonacci(n - 1) + getFibonacci(n - 2);
    }
}