Reputation: 165
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!)
Upvotes: 1
Views: 152
Reputation: 63395
You're getting a Stack Overflow. You can get/set the stack size of your current process using getrlimit(2)/setrlimit(2). Here's an example usage:
import Darwin // Unnecessary if you already have Foundation imported
func getStackByteLimit() -> rlimit? {
var limits = rlimit()
guard getrlimit(RLIMIT_STACK, &limits) != -1 else {
perror("Error with getrlimit")
return nil
}
return limits
}
func setStackLimit(bytes: UInt64) -> Bool {
guard let max = getStackByteLimit()?.rlim_max else { return false }
var limits = rlimit(rlim_cur: bytes, rlim_max: max)
guard setrlimit(RLIMIT_STACK, &limits) != -1 else {
perror("Error with setrlimit")
return false
}
return true
}
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))
Upvotes: 4