CODEWITHSUNDEEP
swiftalgorithm
stevenpcurtis
stevenpcurtis

Reputation: 2001

Dynamic programming Fibonacci Swift

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?

Upvotes: 2

Views: 733

Answers (3)

Sulthan
Sulthan

Reputation: 130132

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
}

Upvotes: 6

Amit
Amit

Reputation: 4896

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 ]
}

Upvotes: 0

user1118321
user1118321

Reputation: 26395

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

Upvotes: 1

Related Questions