Java >> Java tutorial >  >> Tag >> Stack

Opnå stabelløs rekursion i Java 8

En trampolin er et mønster til at omdanne stakbaseret rekursion til en tilsvarende løkke. Da sløjfer ikke tilføjer stak rammer, kan dette opfattes som en form for stableless rekursion.

Her er et diagram, jeg fandt nyttigt:

Fra bartdesmet.net

Du kan tænke på en trampolin som en proces, der tager en startværdi; gentager denne værdi; og afslutter derefter med den endelige værdi.

Overvej denne stakbaserede rekursion:

public static int factorial(final int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

For hvert rekursivt kald dette foretager, skubbes en ny ramme. Dette skyldes, at den tidligere frame ikke kan evalueres uden resultatet af den nye frame. Dette vil blive et problem, når stakken bliver for dyb, og vi løber tør for hukommelse.

Heldigvis kan vi udtrykke denne funktion som en loop:

public static int factorial2(int n) {
    int i = 1; 
    while (n > 1) {
        i = i * n;
        n--;
    }
    return i;
}

Hvad sker der her? Vi har taget det rekursive trin og gjort det til iteration inde i en loop. Vi sløjfer, indtil vi har gennemført alle rekursive trin, og lagrer resultatet eller hver iteration i en variabel.

Dette er mere effektivt, da færre rammer vil blive oprettet. I stedet for at gemme en ramme for hvert rekursivt opkald (n rammer), gemmer vi den aktuelle værdi og antallet af tilbageværende iterationer (2 værdier).

Generaliseringen af ​​dette mønster er en trampolin.

public class Trampoline<T>
{
    public T getValue() {
        throw new RuntimeException("Not implemented");
    }

    public Optional<Trampoline<T>> nextTrampoline() {
        return Optional.empty();
    }

    public final T compute() {
        Trampoline<T> trampoline = this;

        while (trampoline.nextTrampoline().isPresent()) {
            trampoline = trampoline.nextTrampoline().get();
        }

        return trampoline.getValue();
    }
}

Trampoline kræver to medlemmer:

  • værdien af ​​det aktuelle trin;
  • den næste funktion at beregne, eller intet, hvis vi er nået til det sidste trin

Enhver beregning, der kan beskrives på denne måde, kan "trampolines".

Hvordan ser dette ud for factorial?

public final class Factorial
{
    public static Trampoline<Integer> createTrampoline(final int n, final int sum)
    {
        if (n == 1) {
            return new Trampoline<Integer>() {
                public Integer getValue() { return sum; }
            };
        }

        return new Trampoline<Integer>() {
            public Optional<Trampoline<Integer>> nextTrampoline() {
                return Optional.of(createTrampoline(n - 1, sum * n));
            }
        };
    }
}

Og for at ringe:

Factorial.createTrampoline(4, 1).compute()

Noter

  • Boksing vil gøre dette ineffektivt i Java.
  • Denne kode blev skrevet på SO; det er ikke blevet testet eller endda kompileret

Yderligere læsning

  • Java Basics:Sådan fungerer opkald
  • Eliminering af stakke og rekursion
  • Wikipedia
  • Hop trampolinen i C# – stakvenlig rekursion
  • Omvendt trampolin
  • Hvad er en trampolinfunktion?

Java tag