Dynamic programming Fibonacci Swift

Question

I'm trying to covert an implementation below to Swift and having difficulty:

var mem = [];
var fibRecursiveMem = function (n) {
    if (mem[n]) return mem[n];
    if (n<=2) mem[n] = 1;
    else {
        mem[n] = fibRecursiveMem(n-1) + fibRecursiveMem(n-2);
    }
    return mem[n];
}

from: https://dev.to/rattanakchea/dynamic-programming-in-plain-english-using-fibonacci-as-an-example-37m1

my implementation in Swift:

var mem = [Int]()
func fib (_ num: Int) -> Int {
    if (mem.count - 1 > num) {
        return mem[num]
    }
    if (num<=2) {mem[num] = 1}
    else {
        mem[num] = fib(num-1) + fib(num-2)
    }
    return mem[num]
}

Produces index out of range errors.

Now I want to follow the general logic of the original algorithm. What am I doing wrong in the translation?

The main mistake is that you can't assign a value in an array with index subscription if the index > the number of items. Then you have to use `append` or `insert`. — vadian, Oct 24 '18 at 05:13
https://stackoverflow.com/questions/40203182/fibonacci-numbers-generator-in-swift-3 — SPatel, Oct 24 '18 at 05:27
The main mistake is that you're using an array [Int], whereas the original code is using a dictionary [Int:Int]. — Zonker.in.Geneva, Dec 12 '20 at 08:03

score 6 · Accepted Answer · edited Dec 16 '20 at 06:44

In this case, it would be better to use a dictionary to implement memory:

var mem = [Int: Int]()
func fib (_ num: Int) -> Int {
    if let cached = mem[num] {
        return cached
    }

    let result: Int

    if (num <= 2) {
        result = 1
    }
    else {
        result = fib(num - 1) + fib(num - 2)
    }

    mem[num] = result
    return result
}

In javascript, the difference between arrays and dictionaries is rather small. Even when mem is declared as an array, it is actually being used as a dictionary.

To use an array, we have to be sure to always append correctly:

var mem = [0, 1, 1] // prefill initial values for 0, 1, 2
func fib (_ num: Int) -> Int {
    if num < mem.count {
        return mem[num]
    }

    let result = fib(num - 1) + fib(num - 2)
    // the recursion has already appended all previous values
    mem.append(result)

    return result
}

score 1 · Answer 2 · answered Oct 24 '18 at 05:25

One way to do it would be to declare the array as containing some elements and initialize them to a known invalid value, like -1. This will create the array elements, and tell you that you haven't written a value to them. Once you know that, you can determine if there's already a value you can look up and return, or if you need to calculate the value for that entry. It would look something like this:

let kUnitialized = -1
var mem = Array(repeating: kUnitialized, count: 100)

func fib (_ num: Int) -> Int {
    if (mem[num] != kUnitialized) {
        return mem[num]
    }
    if (num <= 2) {
        mem[num] = 1
    } else {
        mem[num] = fib(num - 2) + fib(num - 1)
    }
    return mem[num]
}

Note that in this scenario, you can never call fib with an argument larger than the number of elements contained in the array. (In the example, 100.)

Amit · Answer 3 · 2018-10-24T09:06:09.167

0

I tried using array of integers only.

Getting the proper output :

var mem = [Int]()
func fib (_ num: Int) -> Int {
    if (mem.count > num) {
        return mem[num - 1]
    }

    switch num {
    case 2:
        if mem.count == 0 {
            for _ in 0..<2 {
                mem.append(1)
            }
        }
        else if mem.count == 1 {
            mem.append(1)
        }
    case 1:
        if mem.count == 0 {
            mem.append(1)
        }
    default:
        mem.append(fib(num-1) + fib(num-2))
    }

    print(mem)

    return mem[num - 1 ]
}

edited Oct 24 '18 at 09:06

answered Oct 24 '18 at 06:42

Amit

4,837
5
31
46

Unless you merge the branch for `num == 2` and `num == 1`, your algorithm will fail if you first ask for `1` and then for `2`. Also, your `mem[num]` does not work correctly because it is missing `- 1`. `fib(num-1) + fib(num-3)` is not even a correct implementation of the sequence. – Sulthan Oct 24 '18 at 07:03
Ok got the issue.Thank you @Sulthan. I will delete the answer. – Amit Oct 24 '18 at 07:10
Or just fix the issues :) – Sulthan Oct 24 '18 at 07:10
Yes just checking that only :) – Amit Oct 24 '18 at 07:11
@Sulthan: Is it fine now ? As I added few more conditions. Is it a good approach to add more conditions in it ? – Amit Oct 24 '18 at 07:38
`fib(num-1) + fib(num-3)` is still wrong. That *must* be `fib(num-1) + fib(num-2)`. I have added a sample implementation using array to my answer. To see the problem, try `print(fib(6)); print(fib(5))`. If called in sequence, they both print `8`. It's only about moving the `-1` to `return mem[num]` – Sulthan Oct 24 '18 at 08:11
@Sulthan: Changed it thank you :). One more thing in first if loop I am returning `num-1` as returning `num` was causing the same issue. – Amit Oct 24 '18 at 09:09
That's what I meant by moving the `-1` :) – Sulthan Oct 24 '18 at 09:19

Dynamic programming Fibonacci Swift

3 Answers3