function fibonacci(n) {
  if (n <= 1) {
    return 1
  }

  return fibonacci(n - 1) + fibonacci(n - 2);
}

function memoizedFibonacci(n, memo) {
  memo = memo || {}

  if (memo[n]) {
    return memo[n]
  }

  if (n <= 1) {
    return 1
  }
  
  return memo[n] = memoizedFibonacci(n - 1, memo) + memoizedFibonacci(n - 2, memo)
}

function memoizedFibonacci2(n, memo) {
  memo = memo || {}

  if (memo[n]) {
    return memo[n]
  }

  if (n <= 1) {
    return 1
  }
  
  return memo[n] = memoizedFibonacci2(n - 2, memo) + memoizedFibonacci2(n - 1, memo)
}

function memoizer(fun) {
  let cache = {}

  return function(n) {
    if (cache[n] != undefined ) {
      return cache[n]
    } else {
      let result = fun(n)
      cache[n] = result

      return result
    }
  }
}

const fibonacciMemoFunction = memoizer(fibonacci)
const fibonacciMemoFunction2 = memoizer(memoizedFibonacci)