spices of fibonacci, the good, the bad and the ugly. (without doing matrix multiplication!)

fibs_lazy.exs

defmodule Fibonacci do
  def generate(limit) do
    # Create infinite fibonacci stream
    Stream.unfold({0, 1}, fn
      {x, y} -> {x, {y, (x + y)}}
    end)
    |> Enum.take(limit)
  end
end

fibs_linear.py

# https://stackoverflow.com/questions/13440020/big-o-for-various-fibonacci-implementations
# could be faster if you're not looking for a list
def fib(n):
  acc = [0, 1]
  index = 1
  # O(n)
  for _ in range(n - 2):
    # O(1) lookup
    acc.append(acc[index - 1] + acc[index])
    index += 1
  # return O(n) + O(1) = O(n)
  return acc

# awesome visualization => print( list((fib(x) for x in range(number of fibs))))

fibs_memoized.js

function fibMemo(i, cache={0:0, 1:1}) {
  if (cache[i]) return cache[i];
  
  else {
    if (i == 0 || i == 1) return i

    cache[i] = fibMemo(i - 1, cache) + fibMemo(i - 2, cache)
    return cache[i]
  }
}

fibs_memoized.py

# https://stackoverflow.com/questions/18172257/efficient-calculation-of-fibonacci-series
import functools

# O(1) lookup until memory runs out!!
@functools.lru_cache(maxsize=None)
def fib_memo(n):
  if n < 3:
    return 1
  else:
    # O(n)
    return fib_memo(n - 1) + fib_memo(n - 2)
  
# awesome visualization => print( list((fib_memo(x) for x in range(number of fibs))))
#step by step logging recursion depth
def fib_memo(n, cache={0:0, 1:1}):
  if n not in cache:
    print(f"prev cache state{cache}")
    cache[n] = fib_memo(n-1, cache) + fib_memo(n - 2, cache)
    # happens third and last
    print(f"{n} enters by stack pop",cache)
    return cache[n]
  else:
    if n == 1:
      # happens first
      print(f"recurse terminates => {n}")
      return 1
    # happens second and passes value to third
    print(f"current cache value at{n} is {cache[n]}")
    return cache[n]

#print(list(cache.values())) ==> implement cache class or global var
#print(fib_memo(10))