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.
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])
}
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.)
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. Range
s 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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With