In particular if I have the following code:
func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + n) }
}
Will Swift compiler optimize it to a loop? And does it so in a more interesting case below?
func isOdd(n: Int) -> Bool {
if n == 0 { return false; }
else { return isEven(n - 1) }
}
func isEven(n: Int) -> Bool {
if n == 0 { return true }
else { return isOdd(n - 1) }
}
Yes, the swift compiler performs tail call optimisation in some cases:
As a global function, this will use constant stack space on the "Fastest" optimisation level (
-O
).If it is inside a struct it will still use constant stack space. Within a class however, the compiler does not perform tco because the method might be overridden at runtime.
Clang also supports tco for Objective-C but often ARC calls
release
after the recursive call, thus preventing this optimisation, see this article by Jonathon Mah for more details.ARC also seems to prevent TCO in Swift:
No TCO was performed in my tests.
The best way to check is to examine the assembly language code generated by the compiler. I took the code above and compiled it with:
The relevant part of the output
There are no call instructions in the generated code, only conditional jumps (
je
/jne
/jo
/jno
). This clearly suggests that Swift does do tail call optimizations in both cases.In addition, the
isOdd
/isEven
functions are interesting in that the compiler not only seems to perform TCO but also inlines the other function in each case.