Your buildTree
method does not make any tail calls and therefore cannot take advantage of trampolining. Tail calls are an optimization for when the return value of a method is result of another method call. It allows the stack frame to be replaced with that of the function being called. Without tail call optimization, recursive function calls will cause the stack to increase in size, possible resulting in a stack overflow. Your buildTree method does call itself twice, but the original stack frame has to remain so the result of the two function calls can be combined in creating the new Node
.
The JVM has no built in support for tail all optimization, but Scala has a hack for tail calls where a function invokes itself. Scala replaces these recursive functions calls with a jump to the beginning of the function, effectively turning the recursion into iteration. Unfortunately, this doesn't work for co-recursive calls (e.g. when method A calls B which calls A). Trampolining can be used here instead, either based on a special monad, or abusing exception handling. There is no reason to use trampolining elsewhere.