CODEWITHSUNDEEP
swiftfunctional-programming
Sergio
Sergio

Reputation: 603

Tail Recursion (Tail Call Optimization) in Swift 4

I tried to do the following simple function in Swift:

 func sum (n: Int, currentSum: Int = 0) -> Int {
    return n == 0 ? currentSum :
                    sum(n: n-1,
                        currentSum: currentSum + n)
 }

I expected that the compiler would use tail recursion optimization. But I fall into a (literally :-P) stack overflow problem.

Is there any flag I need to set to make the compiler do such optimization, I made any mistake on my code or this compiler optimization is not available?

Thanks!

Upvotes: 6

Views: 641

Answers (2)

soegaard
soegaard

Reputation: 31147

Is there any flag I need to set to make the compiler do such optimization, I made any mistake on my code or this compiler optimization is not available?

In general you can not rely on tail call optimization in Swift due to the choice of automatic reference counting (ARC) for memory management.

If a function needs to deallocate memory, then the compiler inserts code to do that at the end of a function. Thus preventing a call in tail call position to be compiled as a tail call.

Upvotes: 0

Rob Napier
Rob Napier

Reputation: 299305

As Martin notes, you won't get TCO in any case unless you turn on the optimizer (-O), but even in that case, there's no way to guarantee that you'll get TCO, and so you really can't rely on it. Swift is not particularly friendly to recursive algorithms. Typically you'd write this as:

func sum(n: Int) -> Int {
    return (1...n).reduce(0, +)    
}

Or to maintain the same computational pattern (i.e. counting down from n to 1):

func sum(n: Int) -> Int {
    return (1...n).reversed().reduce(0, +)
}

Upvotes: 6

Related Questions