example of a recursive anonymous class in Java

.gitignore

*.class

README.md

See also recursive-lambda. (I consider that repository to supersede this gist.)

These are examples of:

• a recursive anonymous class in Java – RecursiveAnonymousClassUser.java
• a recursive lambda in Java that passes itself to itself and that uses a cast – RecursiveLambdaCombinatoryViaCast.java
• a recursive lambda in Java that passes itself to itself and that uses a nongeneric recursive interface – RecursiveLambdaCombinatoryViaRecursiveInterface.java
• a recursive lambda that passes itself to itself an that uses a generic recursive interface – RecursiveLambdaCombinatoryViaRecursiveGenericInterface.java

(Note: Caching the result of Pow like this isn’t really a good idea. It is very, very unlikely to lead to an increase in performance, due to the large constants associated with HashMap lookup. Also, if this were used long enough to get numerous hits, one would also want to implement cache invalidation.)

Written in 2020 by Eliah Kagan. Documentation updated in 2021. The contents of this gist are offered under the BSD Zero Clause License. See the LICENSE file.

LICENSE

Copyright (c) 2020 Eliah Kagan

Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.

output.txt

Computed value:
12142679563228033424635341670005387510823412249852134553474965420429186337733573950522113279632132533861827280437430273269452841029915940398173430411182083269933946404545020136869419380338251414042875531442565985406552503033233667996441736652003213480656089244292252090808210312439785896218032902176170127861756017124536698116298281842602533210255186053480955933061524637667094463830887945571230260685351509417633645589536626769914449137649123077755519737684583068578918879599753753909678017595991941400665270473836917444425061870070593313079411113896470499576815306856089653147975083837078813853807692146283840500270309165915273697373325243589907048477578684369938226841317387354228256077838398137597907436090474333052912704886170267318211199357998295230090338545289996366725254995944132999294096309469728210654158218428274805099159804242594912934093210407

Accepted value:
12142679563228033424635341670005387510823412249852134553474965420429186337733573950522113279632132533861827280437430273269452841029915940398173430411182083269933946404545020136869419380338251414042875531442565985406552503033233667996441736652003213480656089244292252090808210312439785896218032902176170127861756017124536698116298281842602533210255186053480955933061524637667094463830887945571230260685351509417633645589536626769914449137649123077755519737684583068578918879599753753909678017595991941400665270473836917444425061870070593313079411113896470499576815306856089653147975083837078813853807692146283840500270309165915273697373325243589907048477578684369938226841317387354228256077838398137597907436090474333052912704886170267318211199357998295230090338545289996366725254995944132999294096309469728210654158218428274805099159804242594912934093210407

Correct?
true

RecursiveAnonymousClassUser.java

// Recursive anonymous class in Java
//
// Copyright (c) 2020 Eliah Kagan
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

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

final class RecursiveAnonymousClassUser {
    private static final class Key {
        Key(BigInteger base, int exponent) {
            if (base == null) throw new NullPointerException();
            _base = base;
            _exponent = exponent;
        }

        public boolean equals(Key rhs) {
            return rhs != null && _base.equals(rhs._base)
                               && _exponent == rhs._exponent;
        }

        @Override
        public boolean equals(Object other) {
            try {
                return equals((Key)other);
            } catch (ClassCastException e) {
                return false;
            }
        }

        @Override
        public int hashCode() {
            return Objects.hash(_base, _exponent);
        }

        final BigInteger _base;

        final int _exponent;
    }

    public static void main(String[] args) {
        var memo = new HashMap<Key, BigInteger>();

        var pow = new BiFunction<BigInteger, Integer, BigInteger>() {
            @Override
            public BigInteger apply(BigInteger base, Integer exponent) {
                if (exponent <= 0) {
                    if (exponent == 0) return BigInteger.ONE;

                    throw new IllegalArgumentException(
                            "Negative exponents are not supported.");
                }

                var key = new Key(base, exponent);
                var value = memo.getOrDefault(key, null);
                if (value != null) return value;

                value = apply(base, exponent / 2);
                value = value.multiply(value);
                if (exponent % 2 != 0) value = value.multiply(base);

                memo.put(key, value);
                return value;
            }
        };

        var ans = pow.apply(BigInteger.valueOf(7), 1013);
        System.out.format("Computed value:%n%s%n%n", ans);

        var known = BigInteger.valueOf(7).pow(1013);
        System.out.format("Accepted value:%n%s%n%n", known);

        System.out.format("Correct?%n%b%n", ans.equals(known));
    }
}

RecursiveLambdaCombinatoryViaCast.java

// Effectively recursive lambda in Java, "combinator" technique via casting
//
// Copyright (c) 2020 Eliah Kagan
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Objects;

@FunctionalInterface
interface TriFunction<T, U, V, R> {
    R apply(T t, U u, V v);
}

final class RecursiveLambdaCombinatoryViaCast {
    private static final class Key {
        Key(BigInteger base, int exponent) {
            if (base == null) throw new NullPointerException();
            _base = base;
            _exponent = exponent;
        }

        public boolean equals(Key rhs) {
            return rhs != null && _base.equals(rhs._base)
                               && _exponent == rhs._exponent;
        }

        @Override
        public boolean equals(Object other) {
            try {
                return equals((Key)other);
            } catch (ClassCastException e) {
                return false;
            }
        }

        @Override
        public int hashCode() {
            return Objects.hash(_base, _exponent);
        }

        final BigInteger _base;

        final int _exponent;
    }

    public static void main(String[] args) {
        var memo = new HashMap<Key, BigInteger>();

        TriFunction<Object, BigInteger, Integer, BigInteger> pow
                = (me, base, exponent) -> {
            if (exponent <= 0) {
                if (exponent == 0) return BigInteger.ONE;

                throw new IllegalArgumentException(
                        "Negative exponents are not supported.");
            }

            var key = new Key(base, exponent);
            var value = memo.getOrDefault(key, null);
            if (value != null) return value;

            @SuppressWarnings("unchecked")
            var me_casted =
                (TriFunction<Object, BigInteger, Integer, BigInteger>)me;

            value = me_casted.apply(me, base, exponent / 2);
            value = value.multiply(value);
            if (exponent % 2 != 0) value = value.multiply(base);

            memo.put(key, value);
            return value;
        };

        var ans = pow.apply(pow, BigInteger.valueOf(7), 1013);
        System.out.format("Computed value:%n%s%n%n", ans);

        var known = BigInteger.valueOf(7).pow(1013);
        System.out.format("Accepted value:%n%s%n%n", known);

        System.out.format("Correct?%n%b%n", ans.equals(known));
    }
}

RecursiveLambdaCombinatoryViaRecursiveGenericInterface.java

// Effectively recursive lambda in Java, "combinator" technique via generic
// recursive interface
//
// Copyright (c) 2020 Eliah Kagan
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Objects;

@FunctionalInterface
interface SelfApplicator<T, U, R> {
    R apply(SelfApplicator<T, U, R> me, T t, U u);
}

final class RecursiveLambdaCombinatoryViaRecursiveInterface {
    private static final class Key {
        Key(BigInteger base, int exponent) {
            if (base == null) throw new NullPointerException();
            _base = base;
            _exponent = exponent;
        }

        public boolean equals(Key rhs) {
            return rhs != null && _base.equals(rhs._base)
                               && _exponent == rhs._exponent;
        }

        @Override
        public boolean equals(Object other) {
            try {
                return equals((Key)other);
            } catch (ClassCastException e) {
                return false;
            }
        }

        @Override
        public int hashCode() {
            return Objects.hash(_base, _exponent);
        }

        final BigInteger _base;

        final int _exponent;
    }

    public static void main(String[] args) {
        var memo = new HashMap<Key, BigInteger>();

        SelfApplicator<BigInteger, Integer, BigInteger> pow
                = (me, base, exponent) -> {
            if (exponent <= 0) {
                if (exponent == 0) return BigInteger.ONE;

                throw new IllegalArgumentException(
                        "Negative exponents are not supported.");
            }

            var key = new Key(base, exponent);
            var value = memo.getOrDefault(key, null);
            if (value != null) return value;

            value = me.apply(me, base, exponent / 2);
            value = value.multiply(value);
            if (exponent % 2 != 0) value = value.multiply(base);

            memo.put(key, value);
            return value;
        };

        var ans = pow.apply(pow, BigInteger.valueOf(7), 1013);
        System.out.format("Computed value:%n%s%n%n", ans);

        var known = BigInteger.valueOf(7).pow(1013);
        System.out.format("Accepted value:%n%s%n%n", known);

        System.out.format("Correct?%n%b%n", ans.equals(known));
    }
}

RecursiveLambdaCombinatoryViaRecursiveInterface.java

// Effectively recursive lambda in Java, "combinator" technique via nongeneric
// recursive interface
//
// Copyright (c) 2020 Eliah Kagan
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Objects;

@FunctionalInterface
interface CombinatoryPow {
    BigInteger apply(CombinatoryPow me, BigInteger base, int exponent);
}

final class RecursiveLambdaCombinatoryViaRecursiveInterface {
    private static final class Key {
        Key(BigInteger base, int exponent) {
            if (base == null) throw new NullPointerException();
            _base = base;
            _exponent = exponent;
        }

        public boolean equals(Key rhs) {
            return rhs != null && _base.equals(rhs._base)
                               && _exponent == rhs._exponent;
        }

        @Override
        public boolean equals(Object other) {
            try {
                return equals((Key)other);
            } catch (ClassCastException e) {
                return false;
            }
        }

        @Override
        public int hashCode() {
            return Objects.hash(_base, _exponent);
        }

        final BigInteger _base;

        final int _exponent;
    }

    public static void main(String[] args) {
        var memo = new HashMap<Key, BigInteger>();

        CombinatoryPow pow = (me, base, exponent) -> {
            if (exponent <= 0) {
                if (exponent == 0) return BigInteger.ONE;

                throw new IllegalArgumentException(
                        "Negative exponents are not supported.");
            }

            var key = new Key(base, exponent);
            var value = memo.getOrDefault(key, null);
            if (value != null) return value;

            value = me.apply(me, base, exponent / 2);
            value = value.multiply(value);
            if (exponent % 2 != 0) value = value.multiply(base);

            memo.put(key, value);
            return value;
        };

        var ans = pow.apply(pow, BigInteger.valueOf(7), 1013);
        System.out.format("Computed value:%n%s%n%n", ans);

        var known = BigInteger.valueOf(7).pow(1013);
        System.out.format("Accepted value:%n%s%n%n", known);

        System.out.format("Correct?%n%b%n", ans.equals(known));
    }
}