Peter J. Nicholls Peter J. Nicholls - 24 days ago 7
Swift Question

Why does this multiple recursion fail over a certain number of recursions?

This code adds up all the integers and

number
, however it crashes with
Segmentation fault: 11
(or bad memory access) at
104829
or larger. Why?

import Foundation
func sigma(_ m: Int64) -> Int64 {
if (m <= 0 ) {
return 0
} else {
return m + sigma(m - 1)
}
}
let number: Int64 = 104829
let answer = sigma(number)


nb:
sigma(104828) = 5494507206


Running in terminal on macOS 10.11 on CoreDuo 2 Macbook Pro with 8GB Ram (incase that's relevant!)

Answer

You're getting a Stack Overflow. You can check the stack size of your current process with this code:

import Darwin // Unnecessary if you already have Foundation imported

var limit = rlimit()
getrlimit(RLIMIT_STACK, &limit)
print(limit)

By default, it's 8,388,608 bytes, (2,048 pages of 4,096 bytes).

Yours is a textbook example of an algorithm that cannot be tail call optimized. The result of the recursive call isn't returned directly, but rather, used as an operand for addition. Because of this, the compiler can't generate code to eliminate away stack frames during recursion. They must stay, in order to keep track of the addition that will need to eventually be done. This algorithm can be improved by using an accumulator parameter:

func sigma(_ m: Int64, acc: Int64 = 0) -> Int64 {
   if (m <= 0 ) {
       return acc
   } else {
       return sigma(m - 1, acc: acc + m)
   }
}

In this code, the result of the recursive call is returned directly. Because of this, the compiler can write code that removed intermediate stack frames. This should prevent stack overflows.

But really, you can just do this in constant time, without any recursive non-sense :p

func sum(from start: Int64 = 0, to end: Int64) -> Int64 {
    let count = end - start + 1

    return (start * count + end * count) / 2
}

print(sum(to: 50))