A concise way to not execute a loop now that C-Sty

Question

Imagine we have this code which works perfectly for n >= 0.

func fibonacci(n: Int) -> Int {
    var memo = [0,1]
    for var i = 2; i <= n; i++ {
        memo.append(memo[i-1] + memo[i-2])
    }
    return memo[n]
}

If I remove the C-style for loop due to upcoming changes to Swift 3.0, I get something like this:

func fibonacci(n: Int) -> Int {
    var memo = [0,1]
    for i in 2...n {
        memo.append(memo[i-1] + memo[i-2])
    }
    return memo[n]
}

While this works fine for n >= 2, it fails for the numbers 0 and 1 with this error message:

fatal error: Can't form Range with end < start

What's the most concise way to fix this code so it works properly for 0 and 1?

(Note: It's okay, and even desirable, for negative numbers to crash the app.)

---

Note: I realize I could add a guard statement:

guard n >= 2 else { return memo[n] }

... but I'm hoping there is a better way to fix just the faulty part of the code (2...n).

For example, if there was a concise way to create a range that returns zero elements if end < start, that would be a more ideal solution.

Answer 1

To do this in a way that works for n < 2, you can use the stride method.

let startIndex = 2
let endIndex = n

for i in stride(from: startIndex, through: endIndex, by: 1) {
    memo.append(memo[i-1] + memo[i-2])
}

Answer 2

As it turns out, the variable i will always be equal to the count of the memoizing array, so you can just use that as your loop condition:

func fibonacci(n: Int) -> Int {
  var memo = [0,1]
  while n >= memo.count {
    memo.append(memo[memo.count-1] + memo[memo.count-2])
  }
  return memo[n]
}

Alternatively, you could express the loop as a recursive function:

func fibonacci(n: Int) -> Int {
  var memo = [0,1]
  func rec(i: Int) -> Int {
    if i >= memo.count { memo.append(rec(i-2) + rec(i-1)) }
    return memo[i]
  }
  return rec(n)
}

Really, though, if is the best solution here. Ranges don't allow the end to be smaller than the beginning by design. The extra line for:

func fibonacci(n: Int) -> Int {
  if n < 2 { return n }
  var memo = [0,1]
  for i in 2...n {
    memo.append(memo[i-1] + memo[i-2])
  }
  return memo[n]
}

Is readable and understandable. (To my eye, the code above is better than the for ;; version)

Answer 3

@Marc's answer is great: https://stackoverflow.com/a/34324032/1032900

But the stride syntax is too long for frequent usage, so I made it a little more pleasant for the common i++ usages...

extension Strideable {
  @warn_unused_result
  public func stride(to end: Self) -> StrideTo<Self> {
    return stride(to: end, by: 1)
  }
}

extension Strideable {
  @warn_unused_result
  public func stride(thru end: Self) -> StrideThrough<Self> {
    return stride(through: end, by: 1)
  }
}

So use like this:

for i in startPos.stride(to: endPos) {
  print("pos at: \(i)")
}

Answer 4

You can easily create a valid range with the max() function:

for i in 2 ..< max(2, n+1) {
    memo.append(memo[i-1] + memo[i-2])
}

This evaluates to an empty range 2 ..< 2 if n < 2.

It is important to use the ..< operator which excludes the upper bound because 2 ... 1 is not a valid range.

But in this function I would simply treat the special cases first

func fibonacci(n: Int) -> Int {
    // Let it crash if n < 0:
    precondition(n >= 0, "n must not be negative")

    // Handle n = 0, 1:
    if n <= 1 {
        return n
    }

    // Handle n >= 2:
    var memo = [0,1]
    for i in 2 ... n {
        memo.append(memo[i-1] + memo[i-2])
    }
    return memo[n]
}

(Note that your memo array is set to the initial value [0, 1] for each function call, so the values are not really "memoized". Without memoization you don't need an array, it would suffice to keep the last two numbers to compute the next.)