Fibonacci in linear time by using an extra pointer

Question

I have a function to find the nth number in a Fibonacci sequence, in which I am recursively calling the function. The sum is stored in a class variable and I have an extra pointer I increment every time the function gets called.

This extra pointer is the gate keeper which dictates the base case of when to exit from the loop. The performance I get, using this algorithm is, \$O(n)\$ linear time and with \$O(1)\$space.

I get the expected answer but I am confused if this an acceptable solution from a coding interview stand point.

var x = 0
var sum = 0
func myFibonacci(of n: Int, a: Int, b:Int) -> Int {
  x+=1
  if (x == n) {
    return sum
  } else {
    sum = a+b
    return myFibonacci(of: n, a: b, b: sum)
  }
}

let finalAns = myFibonacci(of: 9, a: 0, b: 1)
print("The nth number in Fibonacci sequence is \(finalAns)")

Output: 34

Time complexity: \$O(n)\$ linear time

Space complexity \$O(1)\$

Is this an acceptable solution for a coding interview?

Answer 1

Your function uses global variables, which is bad for several reasons:

• The variables must be reset before the function can be called again.
• The variables can be modified from outside of your function, causing wrong results.
• The function is not thread-safe.

In addition,

• The program logic is not immediately obvious (at least it wasn't to me).
• Calling the function with n <= 0 causes an integer overflow.

Global variables are often problematic, and here they can be easily avoided, making the code not only safer, but also simpler.

First, the global sum variable is elimitated by making it local:

var x = 0
func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    x += 1
    if (x == n) {
        return b
    } else {
        let sum = a + b
        return myFibonacci(of: n, a: b, b: sum)
    }
}

or eliminate it completely:

var x = 0
func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    x += 1
    if (x == n) {
        return b
    } else {
        return myFibonacci(of: n, a: b, b: a + b)
    }
}

Now get rid of the global variable x by decrementing n instead in the recursive call:

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    if n == 1 { 
        return b // Recursion terminates here
    }
    return myFibonacci(of: n - 1, a: b, b: a + b)
}

With a slight modification it works for n = 0 as well. Negative arguments should be caught instead of recursing repeatedly until an integer overflow occurs:

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    precondition(n >= 0, "`n` must be non-negative")
    if n == 0 {
        return a // Recursion terminates here
    }
    return myFibonacci(of: n - 1, a: b, b: a + b)
}

This is what I would expect as a recursive implementation in a coding interview (of course you can also implement it iteratively, or use a closed-form expression such as Binet's formula).

As a bonus, you can implement it for negative arguments as well, compare Generalizations of Fibonacci numbers:

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    if n == 0 {
        return a // Recursion terminates here
    } else if n > 0 {
        return myFibonacci(of: n - 1, a: b, b: a + b)
    } else {
        return myFibonacci(of: n + 1, a: b - a, b: a)
    }
}