CODEWITHSUNDEEP
swiftmacosrecursion
Peter J. Nicholls
Peter J. Nicholls

Reputation: 165

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!)

Upvotes: 1

Views: 152

Answers (1)

Alexander
Alexander

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

Related Questions