I have a recursive search of a data structure, which needs to make two recursive calls at the end. One is in tail position, but the other is not, and cannot be. Does Scala optimize the second tail call? Could it? If so, I could try to guess in the code as to which call is more expensive, and call the easy one using normal recursion, and call the hard one as a tail call.
When I try to mark the function as @scala.annotation.tailrec, the compiler errors on the first of the two calls.
A tail recursive means only one recursive call and it is at the end. I suppose that you have to make two because you have tree-like datastructure, what you can do is keep an stack of pending calls and do the recursion over the stack.
Scala eliminates direct tail recursion by rewriting as a loop. @tailrec asks the compiler to fail compilation if it is unable to do this. If you can’t restructure your code to make it tail-recursive you might look at scala.util.control.TailCalls, which gives you a way to swap stack for heap.
I thought about keeping such a stack, but 1) this will add extra complexity to my function and 2) it is not clear whether the space for the data structure is more than the that the system uses for the recursion stack.
BTW, I’m whether you’re right about what “tail recursive” means. The definition is ambiguous. In my case I have two recursive calls. One is a tail call, which can be optimized. The other is not a tail call. Apparently the @tailrec annotation asks the compiler to error if any recursive call is not a tail call.
Are you saying that the compiler already optimizes the recursive call which IS a tail call?
I was considering writing a function within a function (both with the same parameters and return type), the inner of which would have the @tailrec annotation and the other would not. Then change the two recursive calls so that the tail call is a call to the inner function, and the non-tail call is a call to the outer function. This would have the fortunate effect that the compiler could check my annotation, but the unfortunate effect of doubling the call stack, thus the benefit would be dubious.
It would be nice if Scala had a scheme-like do or named-let. This would allow the programmer to force (and declare) some recursive calls to be compiled as efficiently as tail calls, but without requiring all to be.
The Clojure language has such a construct called loop, but doesn’t have normal tail calls. The Clojure construct allows the compiler to verify that the loop is tail-call-optimizable. It would be nice to have both.
“Because all of the recursive calls are in tail-call position, the compiler will generate code similar to a while loop. Each recursive call will be implemented as a jump back to the beginning of the function. Tail-call optimization is discussed in Section 8.9.”
Odersky, Martin; Spoon, Lex; Venners, Bill (2019-12-15). Programming in Scala Fourth Edition: Updated for Scala 2.13 (Kindle Locations 3716-3718). Artima Press. Kindle Edition.
In a word, yes – it’s an automatic optimization, and @tailrec doesn’t change it. All @tailrec does is surface that that isn’t happening: it’s basically a pragma that says, “I expect the compiler to do this, so tell me if I’m wrong”.
It would be great if I could put some sort of @tailrec at the call site rather than (or in addition to) the definition site.
I suspect there might be a slight misunderstanding here. I am 90% sure that the compiler will only optimize a method when all recursive calls are tail calls (and when the methods can’t be overridden). But indeed adding @tailrec does not change whether or not the method will be optimized.
Actually I stand corrected. It looks like the compiler effectively does optimize the call that is in tail position. Despite what the error message and the books say. In that case I agree that the annotation should also work when used at the call site.
Probably such stack would consume as much memory. But that tasks stack would live in the heap (which is usually orders of magnitude bigger than the system call stack). So the point remains, do not blow the stack in case the algorithm have to make many iterations.
No, your function can not be optimized, because the complete function is rewritten to a loop if and only if only one recursive call is done and it is done at the end. Again, as Rob said, you may want to give a look to tail calls.
Finally, I do not see what would be the value of the annotation at use site.
The algorithm being a recursion, a tail recursion, a trampolined recursion, a while loop, a call to a JNI, etc. Is an implementation detail, I as an user do not care (and must not). The annotation is there for you as the implementor to ensure your function is tail-recursive.
The logic of a call-site @tailrec notation is to signal to the compiler to issue an error if the following call cannot be tail optimized. I.e., it is probably tail optimizable now, but after someone refactors the code, and they break the intent of the original author they’d be notified.
Or if I accidentally do something like the following, it should issue an error.
acc +
@tailrec
(some-function-call)
However, something like the following would be OK. At least I’d hope it were. And if not I’d get a very useful compiler error.
acc &&
@tailrec
(some-function-call)
Even in the original case, the notation only asks the compiler to confirm the programmers assumption that his code is susceptible to a particular optimization.
Tail recursive method can be optimized even if there are many recursive calls as long as all of them are in return position (i.e. their result is immediately returned).
Example https://scastie.scala-lang.org/du8hmCQlRKCnL9dI4VbwNw :
def collatzSequence(start: Int): List[Int] = {
@annotation.tailrec
def go(elems: ::[Int]): List[Int] = {
elems.head match {
case 1 => elems.reverse
case n if n % 2 == 0 => go(::(n / 2, elems))
case n /* n % 2 != 0 */ => go(::(n * 3 + 1, elems))
}
}
go(::(start, Nil))
}
...
collatzSequence(11)
collatzSequence(15)
Do you have examples where some self-recursive calls are already in tail position but some other can’t easily (manually) be made tail recursive (all within one method of course)?
But even methods where not all recursive calls are in tail position will be partly optimized.
Take these 2 examples. Methods foo have 2 recursive calls, one is a tail call and one isn’t. The method in class A cannot be optimized because it is non-final, while the one in class B can be optimized.
scala> class A {
| def foo(): Int =
| if (math.random() > 0.5)
| foo() + 1
| else
| foo()
| }
class A
scala> final class B {
| def foo(): Int =
| if (math.random() > 0.5)
| foo() + 1
| else
| foo()
| }
class B
scala> :javap -c A#foo
public int foo();
Code:
0: getstatic #21 // Field scala/math/package$.MODULE$:Lscala/math/package$;
3: invokevirtual #25 // Method scala/math/package$.random:()D
6: ldc2_w #26 // double 0.5d
9: dcmpl
10: ifle 22
13: aload_0
14: invokevirtual #29 // Method foo:()I
17: iconst_1
18: iadd
19: goto 26
22: aload_0
23: invokevirtual #29 // Method foo:()I
26: ireturn
scala> :javap -c B#foo
public int foo();
Code:
0: getstatic #19 // Field scala/math/package$.MODULE$:Lscala/math/package$;
3: invokevirtual #23 // Method scala/math/package$.random:()D
6: ldc2_w #24 // double 0.5d
9: dcmpl
10: ifle 22
13: aload_0
14: invokevirtual #27 // Method foo:()I
17: iconst_1
18: iadd
19: goto 25
22: goto 0
25: ireturn
You can see in the bytecode that A#foo contains 2 calls to foo. B#foo contains only one call to foo, and the other call is replaced by a goto instruction.
Good to know. But still the foo methods can be easily made tail-recursive by doing a small refactor (intoducing local tail recursive methods).
Call-site @tailrec annotations maybe convey the intent, but you need to understand the whole original idea present in method implementation to not break it. I assume that if you deliberately keep some self recursive calls tail recursive and some non-tail recursive then the tail recursive ones are much more frequent (e.g. by Theta(lg n) times). If someone that refactors the code doesn’t know that then he can destroy that optimization by changing recursive calls frequencies across the self-recursive method.
Example - quicksort with (logarithmically) bounded stack depth:
def qsort[T: Ordering](range: Range, array: Array[T]): Unit = {
val pivot = findPivot(range, array)
val (leftRange, rightRange) = partition(range, array, pivot)
if (leftRange.size < rightRange.size) {
qsort(leftRange, array) // non-tail recursion on smaller partition
@tailrec qsort(rightRange, array) // tail recursion on bigger partition
} else {
qsort(rightRange, array) // non-tail recursion on smaller partition
@tailrec qsort(leftRange, array) // tail recursion on bigger partition
}
}
Now what if someone refactors the code and inverts the condition in if (leftRange.size < rightRange.size)? qsort stops being stack safe, but is still correct for non-pathological input arrays.
How does this qsort terminate?
Well, it doesn’t 
I forgot to add an if that checks for empty range. However, even after fixing that doesn’t change the reasoning.
I know. I was just pulling your leg.
meanwhile in Java land:
In 2013 Steele made this claim that implementing TCO was something “we” understand how to do. Does anyone know the plan?