使用java 8设计尾递归 [英] Designing tail recursion using java 8

问题描述

我在讲话中尝试了以下示例，以了解尾部递归在java8中。

I was trying out the following example provide in the talk to understand the tail recursion in java8.

@FunctionalInterface
public interface TailCall<T> {
    TailCall<T> apply();

    default boolean isComplete() {
        return false;
    }

    default T result() {
        throw new Error("not implemented");
    }

    default T get() {
        return Stream.iterate(this, TailCall::apply).filter(TailCall::isComplete)
                                                .findFirst().get().result();
    }
}

使用TailCall的实用程序类

Utility class to use the TailCall

public class TailCalls {
    public static <T> TailCall<T> call(final TailCall<T> nextcall) {
        return nextcall;
    }

    public static <T> TailCall<T> done(final T value) {
        return new TailCall<T>() {
            @Override
            public boolean isComplete() {
                return true;
            }

            @Override
            public T result() {
                return value;
            }

            @Override
            public TailCall<T> apply() {
                throw new Error("not implemented.");
            }
        };
    }
}

这是使用Tail递归：

Here is the use of the of Tail recursion :

public class Main {

    public static TailCall<Integer> factorial(int fact, int n) {
        if (n == 1) {
            return TailCalls.done(fact);
        } else {
            return TailCalls.call(factorial(fact * n, n-1));
        }
    }

    public static void main(String[] args) {
        System.out.println(factorial(1, 5).get());
        }
}

它工作正常，但我觉得我们不喜欢t需要 TailCall :: get 来计算结果。根据我的理解，我们可以直接计算结果：

It worked correctly, but I feel like we don't require the TailCall::get to compute the result. As per my understanding we can directly compute the result using:

System.out.println(factorial(1, 5).result());

而不是：

System.out.println(factorial(1, 5).get());

如果我错过 TailCall :: get的要点，请告诉我。 。

推荐答案

示例中有错误。它只是预先形成普通递归，没有尾调用优化。您可以通过将 Thread.dumpStack 添加到基本案例来看到这一点：

There is a mistake in the example. It will just preform plain recursion, without tail call optimization. You can see this by adding Thread.dumpStack to the base case:

if (n == 1) {
    Thread.dumpStack();
    return TailCalls.done(fact);
}

堆栈跟踪看起来像：

java.lang.Exception: Stack trace
    at java.lang.Thread.dumpStack(Thread.java:1333)
    at test.Main.factorial(Main.java:14)
    at test.Main.factorial(Main.java:18)
    at test.Main.factorial(Main.java:18)
    at test.Main.factorial(Main.java:18)
    at test.Main.factorial(Main.java:18)
    at test.Main.main(Main.java:8)

正如您所看到的，有多次调用 factorial 。这意味着在没有尾调用优化的情况下发生普通递归。在这种情况下，调用 get 确实没有意义，因为你从 TailCall 对象> factorial 已经有结果。

As you can see there are multiple calls to factorial. This means that plain recursion takes place, without the tail call optimization. In that case there is indeed no point in calling get since the TailCall object you get back from factorial already has the result in it.

实现此目的的正确方法是返回一个推迟实际调用的新 TailCall 对象：

The right way to implement this is to return a new TailCall object that defers the actual call:

public static TailCall<Integer> factorial(int fact, int n) {
    if (n == 1) {
        return TailCalls.done(fact);
    }

    return () -> factorial(fact * n, n-1);
}

如果还添加 Thread.dumpStack 只有1次致电 factorial ：

If you also add the Thread.dumpStack there will be only 1 call to factorial:

java.lang.Exception: Stack trace
    at java.lang.Thread.dumpStack(Thread.java:1333)
    at test.Main.factorial(Main.java:14)
    at test.Main.lambda$0(Main.java:18)
    at java.util.stream.Stream$1.next(Stream.java:1033)
    at java.util.Spliterators$IteratorSpliterator.tryAdvance(Spliterators.java:1812)
    at java.util.stream.ReferencePipeline.forEachWithCancel(ReferencePipeline.java:126)
    at java.util.stream.AbstractPipeline.copyIntoWithCancel(AbstractPipeline.java:498)
    at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:485)
    at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471)
    at java.util.stream.FindOps$FindOp.evaluateSequential(FindOps.java:152)
    at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
    at java.util.stream.ReferencePipeline.findFirst(ReferencePipeline.java:464)
    at test.TailCall.get(Main.java:36)
    at test.Main.main(Main.java:9)

这篇关于使用java 8设计尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！