使用java 8设计尾递归

Question

我试图从下面的例子中提供谈话了解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的实用程序类

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递归的用法:

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());
        }
}

它工作正常,但我觉得我们不需要TailCall::get计算结果.根据我的理解,我们可以使用以下方法直接计算结果:

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

代替:

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

如果我错过了这个要点,请告诉我TailCall::get.

Answer 1

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

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已经有了结果.

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

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:

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)