Calculating the Fibonacci Sequence in Python

In mathematics, the Fibonacci sequence is built up by summing the previous two numbers in the sequence and appending it to the sequence. The sequence starts with 0 and 1, therefore the first ten numbers of the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

There are many methods of implementing this in Python, however I have written three methods of achieving this.

Solution 1: Use a for loop to append to a list on the fly.

def fibonacci_list(previous, current, maximum):
    fib_nums = []
    for num in range(maximum):
        fib_nums.append(previous)
        print('Fib', num, '=', previous)
        previous, current = current, previous + current
    return fib_nums

# The function can be called as follows:
if __name__ == '__main__':
    fibonacci_list(previous=0, current=1, maximum=101)

Solution 2: Use a while loop to yield each element as it is calculated.

def fibonacci_generator(previous, current, maximum):
    count = 0
    while count < maximum:
        previous, current = current, previous + current
        yield previous
        count += 1
        print(f'Fib {count} = {previous}')

# `pass` statement is there only because the function requires it.
if __name__ == '__main__':
    for num in fibonacci_generator(previous=0, current=1, maximum=101):
        pass

Solution 3: Use a recursive function with the lru_cache decorator from functools to implement memoization

This implementation is perhaps the most interesting of them all because it gives an insight into recursive functions and memoization.

# The code below will not work as intended.
# It will grind to a halt as the call stack keeps increasing.
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n > 1:
        return fibonacci(n - 1) + fibonacci(n - 2)

if __name__ == "__main__":
    for n in range(0, 101):
        print('Fib', n, '=', fibonacci(n))

However, after importing 'lru_cache' function from the functools built-in module and applying it as a decorator to the fibonacci_recursive function, then it will work as the implemented memoization means that the result from each run is cached and carried forward into the next recursive function call. This prevents the call stack from getting larger on each call like it was in the function above.

from functools import lru_cache  # Added

@lru_cache(maxsize=1000)  # Added
def fibonacci_recursive(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    elif num > 1:
        return fibonacci_recursive(num - 1) + fibonacci_recursive(num - 2)

if __name__ == "__main__":
    for num in range(0, 101):
        print('Fib', num, '=', fibonacci_recursive(num))

Finally, here is solution 1 in the equivalent JavaScript.

function fibonacciArray(previous, current, maximum) {
  fibNums = []
  for (let num = 1; num < maximum; num++) {
    fibNums.push(previous)
    console.log(`Fib ${num} = ${previous}`)
    current = [previous + current, previous = current][0];
  }
  return fibNums
}


fibonacciArray(previous = 0,current = 1,maximum = 101)