5 Ways of Generating Fibonacci Numbers

March 7, 2020 4-minute read

This is just a quick note about 5 ways of generating Fibonacci numbers. Here, I want to create a function whose argument is an int number “n” (representing which number to return in the Fibonacci sequence). This function will return the Fibonacci number I want. In my definition for this question, I want the Fibonacci sequence to start from 0.

1. Recursion without Cache

1
2
3
4
5


def fib(n):
    if n <= 2:
        return n - 1
    else:
        return fib(n - 1) + fib(n - 2)

The time complexity of this function is $O(1.618^{n})$ by solving the characteristic equation of F(n) = F(n-1) + F(n-2).

2. Recursion with Cache

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def fib(n):
    if n <= 2:
        return n - 1
    elif n in fib.cache:
        return fib.cache[n]
    else:
        result = fib(n - 1) + fib(n - 2)
        fib.cache[n] = result
        return result
fib.cache = {}

By cacheing to avoid repeated calculation, we could significantly reduce the time complexity of the recursion method. The time complexity of this approach is $O(n)$.

3. Induction without Cache

1
2
3
4
5
6
7


def fib(n):
    if n <= 2:
        return n - 1
    a, b = 0, 1
    for i in range(n - 2):
        a, b = b, a + b
    return b

The time complexity of the third approach is $O(n^{2})$.

4. Induction with Cache

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def fib(n):
    fib_list = []
    if n <= 2:
        fib_list.append(n - 1)
        return n - 1
    a, b = 0, 1
    for i in range(n - 2):
        a, b = b, a + b
        fib_list.append(b)
    return b

Here, maybe you don’t see the point of cacheing the Fibonacci sequence in the induction case since we still let the computer do the calculation which doesn’t use the value in our list. However, cache will be useful in our next step.

The time complexity of this method is O($n^{2}$).

5. Math Formula

1
2
3
4
5
6
7
8


def fib(n):
    if n == 1:
        return 0
    sqrt_5 = 5**.5
    term1 = (1 + sqrt_5) / 2
    term2 = (1 - sqrt_5) / 2
    result = (term1**(n - 1) - term2**(n - 1)) / sqrt_5
    return int(result)

The time complexity of the mathematical method is $O(1)$ since it only computes once using the formula. It’s the most efficient way.

What if we want to print the first n numbers (Fibonacci sequence) instead of No. n Fibonacci number?

1. Recursion without Cache

1
2
3
4
5
6
7
8


def fib(n):
    def f(k):
        if k <= 2:
            return k - 1
        else:
            return f(k - 1) + f(k - 2)
    for i in range(1, n + 1):
        return f(i)

Since there’s no cache here, as you could imagine, the time complexity of this method would still be $O(1.618^{n})$ since for each number, we only add one step to let the function print itself. It will be really time-consuming when it becomes large such as 100, not to mention even larger numbers.

2. Recursion with Cache

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def fib(n):
    def f(k):
        if k <= 2:
            return k - 1
        elif k in f.cache:
            return f.cache[k]
        else:
            result = f(k - 1) + f(k - 2)
            f.cache[k] = result
            return result
    f.cache = {}
    f(n)
    return list(f.cache.values())

Same, after computing and cacheing, for every number in our cache, we only need to print it, so the time complexity doesn’t change and still remains $O(n)$.

3. Induction without Cache

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def fib(n):
    def f(k):
        if k <= 2:
            return k - 1
        a, b = 0, 1
        for i in range(k - 2):
            a, b = b, a + b
        return b
    for i in range(1, n + 1):
        print(f(i))

Time complexity of this method is $O(n^2)$

4. Induction with Cache

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


def fib(n):
    fib_list = [0, 1]

    def f(k):
        if k <= 2:
            return k - 1
        a, b = 0, 1
        for i in range(k - 2):
            a, b = b, a + b
            fib_list.append(b)
        return b

    f(n)
    return fib_list[:n]

Using cache, we could easily return the whole Fibonacci sequence with the time complexity $O(n^2)$

5. Math Formula

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


def fib(n):
    fib_list = [0]
    def f(k):
        if k == 1:
            return 0
        else:
            for i in range(2, k + 1):
                sqrt_5 = 5**.5
                term1 = (1 + sqrt_5) / 2
                term2 = (1 - sqrt_5) / 2
                result = (term1**(i - 1) - term2**(i - 1)) / sqrt_5
                fib_list.append(int(result))
    f(n)
    return fib_list

The time complexity of this algorithm is $O(n)$.