fib.java

package com.company;

import java.util.HashMap;
import java.util.Map;
import java.util.function.BiFunction;
import java.util.function.Function;

public class Main {
    public static void main(String[] args) {
        Function<Long, Long> fib = cachedRecursive(
                (n, f) -> n <= 2
                        ? 1L
                        : f.apply(n - 1) + f.apply(n - 2));

        var result = fib.apply(50L);
        System.out.println(result); // 12586269025
    }

    public static <T, R> Function<T, R> cachedRecursive(BiFunction<T, Function<T, R>, R> value) {
        return cachedRecursive(value, 50);
    }

    public static <T, R> Function<T, R> cachedRecursive(BiFunction<T, Function<T, R>, R> value, int maximalCacheSize) {
        Map<T, R> cache = new HashMap<>(maximalCacheSize);
        return t -> new Object() {
            Function<T, R> adj = u -> {
                if (cache.containsKey(u)) {
                    return cache.get(u);
                } else { // Can't use computeIfAbsent, https://bugs.openjdk.java.net/browse/JDK-8071667
                    var result = value.apply(u, this.adj);
                    cache.put(u, result);
                    return result;
                }
            };
        }.adj.apply(t);
    }
}

// Or use a nicer language, like Swift: https://gist.github.com/clausjoergensen/408caa733f29236263d647787a1750d9