The question is: How can I implement the method below ( toListPreOrderLeft) using tail recursion?

 public List<A> toListPreOrderLeft() {
        return toListPreOrderLeft_(this, list()).eval();
    }

    private TailCall<List<A>> toListPreOrderLeft_(TreeNode<A> tree, List<A> list) {
        return ???
    }

Details:

Lets say I have this tree:

transforming it into a list using pre-order-left algorithm will produce the list : [4,2,1,3,6,5,7]

I could implement this algorithm using stack-recursion in the tree class:

 public List<A> toListPreOrderLeft() {
            return list(this.value)
                    .concat(this.left.toListPreOrderLeft())
                    .concat(this.right.toListPreOrderLeft());
        }

where concat just concatenates two lists, and this refers to the tree node on which I am calling the method.
(I am using my custom implementation of List and Tree).

But this implementation will overflow the stack if I have a tree inserted in this order: 100000,99999,99998,99997,...,3,2,1.

Here is the class I use to represent the tail-recursive calls:

public abstract class TailCall<T> {

    public abstract TailCall<T> nextCall();

    public abstract T eval();

    public abstract boolean isIntermediate();

    //this constructor is to prevent this class from being extended by other classes
    private TailCall() {
    }

    public static <T> TailCall<T> terminalCall(T t) {
        return new TerminalCall<>(t);
    }

    public static <T> TailCall<T> intermediateCall(Supplier<TailCall<T>> nextCall) {
        return new IntermediateCall<>(nextCall);
    }

    private static class TerminalCall<T> extends TailCall<T> {
        private final T t;

        private TerminalCall(T t) {
            this.t = t;
        }

        @Override
        public T eval() {
            return t;
        }

        @Override
        public TailCall<T> nextCall() {
            throw new IllegalStateException("Terminal has no next call");
        }

        @Override
        public boolean isIntermediate() {
            return false;
        }
    }

    private static class IntermediateCall<T> extends TailCall<T> {
        private final Supplier<TailCall<T>> nextCall;

        private IntermediateCall(Supplier<TailCall<T>> nextCall) {
            this.nextCall = nextCall;
        }

        @Override
        public T eval() {
            TailCall<T> tailCall = this;
            while (tailCall.isIntermediate()) {
                tailCall = tailCall.nextCall();
            }
            return tailCall.eval();
        }

        @Override
        public TailCall<T> nextCall() {
            return nextCall.get();
        }

        @Override
        public boolean isIntermediate() {
            return true;
        }
    }
}

And here is an example of how to implement a method that transforms the tree into a list using in-order traversal and using tail-recursion with this class (we keep rotating the tree until it becomes like an ordered linked list):

   public List<A> toListInOrderLeft() {
        return toListInOrderLeft_(this, list()).eval();
    }

    private TailCall<List<A>> toListInOrderLeft_(TreeNode<A> tree, List<A> accumulator) {
        return tree.isEmpty()
                ? TailCall.terminalCall(accumulator)
                : tree.right().isEmpty()
                ? intermediateCall(() -> toListInOrderLeft_(tree.left(), accumulator.prepend(tree.value()))) //prepend adds value at the start of a list
                : intermediateCall(() -> toListInOrderLeft_(tree.rotateLeft(), accumulator));
    }

Here is a brief explanation of the code in the question:

• TailCall is a class that represents a recursive call, so instead of doing a recursive call by pushing a new stackframe, we create an instance of TailCall which can be intermediate or terminal subclass depending on whether the recursive call is the last call or there will be a next call embedded in it (in the TailCall object) using a Supplier (which achieves lazy evaluation). So at any point in time, we either have 1 referenced object representing the whole recursion chain, or at most 2 referenced objects representing it (and this latter case happens when we start evaluating the TailCall's next call using eval method

• Now that that was said, it is easy to see how the example method toListInOrderLeft works, it calls a helper method which returns a TailCall (representing the first recursive call) and then calls eval on this returned object to evaluate the recursive calls till the end. As for the helper method, it takes an accumulator (initially an empty list) and starts appending values to it taken from the tree's nodes. And when the terminal condition is reached, we return this accumulator wrapped in a terminal call from the helper method.

CodePudding user response：

The TailCall cannot really be used as a stack to remember things. It can model tail recursion, but the recursive implementation of toListPreorderLeft is not just tail recursive.

Many languages provide "monadic" classes similar to TailCall, but with something like a TailCall.then(...) method that you can use to chain stuff together. Without this capability, you will need to make another stack -- either explicitly or implicitly.

Your toListInorderLeft method has the same problem, but you cheated by mutating the tree, effectively using the tree as your stack. That trick won't work for preorder.

You can solve this problem by translating the recursive algorithm into "continuation passing style". This implicitly makes a stack of lambda functions:

class TreeNode<A> {
    
    TreeNode<A> left;
    TreeNode<A> right;
    A value;

    ...

    public TailCall<List<A>> toListPreOrderLeft() {
        return _toListPreOrderLeft(new ArrayList<>(), null);
    }

    private TailCall<List<A>> _toListPreOrderLeft(List<A> accumulator, Function<List<A>, TailCall<List<A>>> continuation) {
        accumulator.add(this.value);
        if (this.left != null && this.right != null) {
            final Function<List<A>, TailCall<List<A>>> cont2 = (accum) ->
                    this.right._toListPreOrderLeft(accum, continuation);
            return TailCall.intermediateCall(() -> this.left._toListPreOrderLeft(accumulator, cont2));
        } else if (this.right != null) {
            return TailCall.intermediateCall(() -> this.right._toListPreOrderLeft(accumulator, continuation));
        } else if (this.left != null) {
            return TailCall.intermediateCall(() -> this.right._toListPreOrderLeft(accumulator, continuation));
        } else if (continuation != null) {
            return TailCall.intermediateCall(() -> continuation.apply(accumulator));
        }
        return TailCall.terminalCall(accumulator);
    }
}

The continuation parameter captures the work that remains to be done after the current call ends. The links from cont2 to continuation form an implicit stack.

Please note that this is a horrible way to avoid stack overflows. It's much better to understand the algorithm and write a nice iterative implementation like this:

    public List<A> toListPreOrderLeft() {
        final List<A> accumulator = new ArrayList<>();
        final List<TreeNode<A>> treeStack = new ArrayList<>();
        TreeNode<A> n = this;
        for (;;) {
            accumulator.add(n.value);
            if (n.left != null) {
                if (n.right != null) {
                    treeStack.add((n.right));
                }
                n = n.left;
            } else if (n.right != null) {
                n = n.right;
            } else if (!treeStack.isEmpty()) {
                n = treeStack.remove(treeStack.size()-1);
            } else {
                break;
            }
        }
        return accumulator;
    }