README.md

Fibonacci memoized - recursive anonymous functions

This gist contains examples of recursive anonymous functions, implemented with various techniques, in C++, Java, and C#.

Files named like *.linq.cs are really .linq files. The extra .cs suffix is to get C# syntax highlighting.

anonymous-class.java

import java.math.BigInteger;
import java.util.HashMap;
import java.util.function.IntFunction;

final class AnonymousClassFibonacci {
    public static void main(String[] args) {
        var memo = new HashMap<Integer, BigInteger>();
        memo.put(0, BigInteger.ZERO);
        memo.put(1, BigInteger.ONE);

        var fib = new IntFunction<BigInteger>() {
            @Override
            public BigInteger apply(int n) {
                if (n < 0)
                    throw new IllegalArgumentException("n must be nonnegative");

                var result = memo.getOrDefault(n, null);
                if (result != null) return result;

                result = apply(n - 2).add(apply(n - 1));
                memo.put(n, result);
                return result;
            }
        };

        System.out.println(fib.apply(10));
        System.out.println(fib.apply(1000));
    }
}

CMakeLists.txt

cmake_minimum_required(VERSION 3.0.0)
project(fibonacci-memoized VERSION 0.1.0)

include(CTest)
enable_testing()

set(CMAKE_CXX_EXTENSIONS OFF)
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

if(MSVC)
    # cl and clang-cl accept /W4 (but -Weverything will override in clang-cl).
    string(REGEX REPLACE /W[123] /W4 CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS})

    # cl and clang-cl accept /permissive- for stricter conformance.
    add_compile_options(/permissive-)
else()
    # gcc/g++ and clang/clang++ require comparably strict conformance to
    # /permissive- unless -fpermissive is passed. But they accept -pedantic
    # for even more conformance warnings, and -pedantic-errors for errors.
    add_compile_options(-pedantic-errors)
endif()

if(${CMAKE_CXX_COMPILER_ID} STREQUAL "Clang")
    # Clang accepts -Weverything with both clang/clang++ and clang-cl.
    # We will keep all but a few of the warnings that -Weverything enables.
    add_compile_options(
        -Weverything
        -Wno-c++98-compat
        -Wno-c++98-compat-pedantic

        # FIXME: Suppress (just) in Boost header, and just with Clang/MSVC
        # (regular Clang, and also the MSVC compiler, don't need them).
        #-Wno-comma
        #-Wno-deprecated
        #-Wno-documentation
        #-Wno-float-conversion
        #-Wno-float-equal
        #-Wno-missing-noreturn
        #-Wno-old-style-cast
        #-Wno-sign-conversion
        #-Wno-reserved-id-macro
        #-Wno-undef
        #-Wno-zero-as-null-pointer-constant
    )
elseif(MSVC)
    # cl but not clang-cl accepts /Za to reject Microsoft extensions.
    add_compile_options(/Za)

    # cl but not clang-cl accepts /analyze for static analysis (default rules).
    add_compile_options(/analyze)
else()
    # Enable most warnings.
    add_compile_options(-Wall -Wextra)
endif()

find_package(Boost REQUIRED)

add_executable(recursive-lambda-stdfunction
    recursive-lambda-stdfunction.cpp
)

add_executable(recursive-lambda-combinatory
    recursive-lambda-combinatory.cpp
)

add_executable(recursive-lambda-combinatory-wrapped
    recursive-lambda-combinatory-wrapped.cpp
)

target_link_libraries(recursive-lambda-stdfunction PRIVATE Boost::boost)
target_link_libraries(recursive-lambda-combinatory PRIVATE Boost::boost)
target_link_libraries(recursive-lambda-combinatory-wrapped PRIVATE Boost::boost)

set(CPACK_PROJECT_NAME ${PROJECT_NAME})
set(CPACK_PROJECT_VERSION ${PROJECT_VERSION})
include(CPack)

lambda-combinatory-dynamic-wrapped.linq.cs

<Query Kind="Statements">
  <Namespace>System.Numerics</Namespace>
</Query>

var memo = new Dictionary<int, BigInteger> { {0, 0}, {1, 1} };

Func<int, BigInteger> fib = n => {
    if (n < 0) throw new ArgumentOutOfRangeException(paramName: nameof(n));

    Func<dynamic, int, BigInteger> f = (me, k) => {
        if (memo.TryGetValue(k, out var result)) return result;
        
        result = me(me, k - 2) + me(me, k - 1);
        memo.Add(k, result);
        return result;
    };
    
    return f(f, n);
};

fib(10).Dump();
fib(1000).Dump();

lambda-combinatory-dynamic.linq.cs

<Query Kind="Statements">
  <Namespace>System.Numerics</Namespace>
</Query>

var memo = new Dictionary<int, BigInteger> { {0, 0}, {1, 1} };

Func<dynamic, int, BigInteger> fib = (me, n) => {
    if (n < 0) throw new ArgumentOutOfRangeException(paramName: nameof(n));
    if (memo.TryGetValue(n, out var result)) return result;
    
    result = me(me, n - 2) + me(me, n - 1);
    memo.Add(n, result);
    return result;
};

fib(fib, 10).Dump();
fib(fib, 1000).Dump();

lambda-combinatory-object-wrapped.linq.cs

<Query Kind="Statements">
  <Namespace>System.Numerics</Namespace>
</Query>

var memo = new Dictionary<int, BigInteger> { {0, 0}, {1, 1} };

Func<int, BigInteger> fib = n => {
    if (n < 0) throw new ArgumentOutOfRangeException(paramName: nameof(n));

    Func<dynamic, int, BigInteger> f = (me, k) => {
        if (memo.TryGetValue(k, out var result)) return result;
        
        var me_casted = (Func<object, int, BigInteger>)me;
        result = me_casted(me, k - 2) + me_casted(me, k - 1);
        memo.Add(k, result);
        return result;
    };
    
    return f(f, n);
};

fib(10).Dump();
fib(1000).Dump();

lambda-combinatory-object.linq.cs

<Query Kind="Statements">
  <Namespace>System.Numerics</Namespace>
</Query>

var memo = new Dictionary<int, BigInteger> { {0, 0}, {1, 1} };

Func<object, int, BigInteger> fib = (me, n) => {
    if (n < 0) throw new ArgumentOutOfRangeException(paramName: nameof(n));
    if (memo.TryGetValue(n, out var result)) return result;
    
    var me_casted = (Func<object, int, BigInteger>)me;
    result = me_casted(me, n - 2) + me_casted(me, n - 1);
    memo.Add(n, result);
    return result;
};

fib(fib, 10).Dump();
fib(fib, 1000).Dump();

lambda-combinatory-wrapped.java

import java.math.BigInteger;
import java.util.HashMap;
import java.util.function.BiFunction;
import java.util.function.IntFunction;

final class LambdaCombinatoryFibonacciWrapped {
    public static void main(String[] args) {
        var memo = new HashMap<Integer, BigInteger>();
        memo.put(0, BigInteger.ZERO);
        memo.put(1, BigInteger.ONE);

        IntFunction<BigInteger> fib = n -> {
            if (n < 0)
                throw new IllegalArgumentException("n must be nonnegative");

            BiFunction<Object, Integer, BigInteger> f = (me, k) -> {
                var result = memo.getOrDefault(k, null);
                if (result != null) return result;

                @SuppressWarnings("unchecked")
                var me_casted = (BiFunction<Object, Integer, BigInteger>)me;
                result = me_casted.apply(me, k - 2).add(me_casted.apply(me, k - 1));
                memo.put(k, result);
                return result;
            };

            return f.apply(f, n);
        };

        System.out.println(fib.apply(10));
        System.out.println(fib.apply(1000));
    }
}

lambda-combinatory.java

import java.math.BigInteger;
import java.util.HashMap;
import java.util.function.BiFunction;

final class LambdaCombinatoryFibonacci {
    public static void main(String[] args) {
        var memo = new HashMap<Integer, BigInteger>();
        memo.put(0, BigInteger.ZERO);
        memo.put(1, BigInteger.ONE);

        BiFunction<Object, Integer, BigInteger> fib = (me, n) -> {
            if (n < 0)
                throw new IllegalArgumentException("n must be nonnegative");

            var result = memo.getOrDefault(n, null);
            if (result != null) return result;

            @SuppressWarnings("unchecked")
            var me_casted = (BiFunction<Object, Integer, BigInteger>)me;
            result = me_casted.apply(me, n - 2).add(me_casted.apply(me, n - 1));
            memo.put(n, result);
            return result;
        };

        System.out.println(fib.apply(fib, 10));
        System.out.println(fib.apply(fib, 1000));
    }
}

lambda-reassigned.linq.cs

<Query Kind="Statements">
  <Namespace>System.Numerics</Namespace>
</Query>

var memo = new Dictionary<int, BigInteger> { {0, 0}, {1, 1} };

Func<int, BigInteger> fib = null!;

fib = n => {
    if (n < 0) throw new ArgumentOutOfRangeException(paramName: nameof(n));
    if (memo.TryGetValue(n, out var result)) return result;
    
    result = fib(n - 2) + fib(n - 1);
    memo.Add(n, result);
    return result;
};

fib(10).Dump();
fib(1000).Dump();

local-function.linq.cs

<Query Kind="Statements">
  <Namespace>System.Numerics</Namespace>
</Query>

var memo = new Dictionary<int, BigInteger> { {0, 0}, {1, 1} };

BigInteger Fib(int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(paramName: nameof(n));
    if (memo.TryGetValue(n, out var result)) return result;
    
    result = Fib(n - 2) + Fib(n - 1);
    memo.Add(n, result);
    return result;
}

Fib(10).Dump();
Fib(1000).Dump();

recursive-lambda-combinatory-wrapped.cpp

#include <iostream>
#include <iterator>
#include <unordered_map>
#include <boost/multiprecision/cpp_int.hpp>

int main()
{
    using boost::multiprecision::cpp_int;

    std::unordered_map<unsigned, cpp_int> memo {{0, 0}, {1, 1}};

    auto fib = [&memo](unsigned n) {
        auto f = [&memo](const auto& me, unsigned k) {
            if (auto p = memo.find(k); p != end(memo)) return p->second;

            cpp_int result = me(me, k - 2) + me(me, k - 1);
            memo.emplace(k, result);
            return result;
        };

        return f(f, n);
    };

    std::cout << fib(10) << '\n';
    std::cout << fib(1000) << '\n';
}

recursive-lambda-combinatory.cpp

#include <iostream>
#include <iterator>
#include <unordered_map>
#include <boost/multiprecision/cpp_int.hpp>

int main()
{
    using boost::multiprecision::cpp_int;

    std::unordered_map<unsigned, cpp_int> memo {{0, 0}, {1, 1}};

    auto fib = [&memo](const auto& me, unsigned n) {
        if (auto p = memo.find(n); p != end(memo)) return p->second;

        cpp_int result = me(me, n - 2) + me(me, n - 1);
        memo.emplace(n, result);
        return result;
    };

    std::cout << fib(fib, 10) << '\n';
    std::cout << fib(fib, 1000) << '\n';
}

recursive-lambda-stdfunction.cpp

#include <functional>
#include <iostream>
#include <iterator>
#include <unordered_map>
#include <boost/multiprecision/cpp_int.hpp>

int main()
{
    using boost::multiprecision::cpp_int;

    std::unordered_map<unsigned, cpp_int> memo {{0, 0}, {1, 1}};

    std::function<cpp_int(unsigned)> fib = [&memo, &fib](unsigned n) {
        if (auto p = memo.find(n); p != end(memo)) return p->second;

        cpp_int result = fib(n - 2) + fib(n - 1);
        memo.emplace(n, result);
        return result;
    };

    std::cout << fib(10) << '\n';
    std::cout << fib(1000) << '\n';
}