## Formula

1, 1, 2, 3, 5, 8, 13, 21.... と続いていく数式

$
Fn = Fn-1 + Fn-2 
$

## Noob

```js
function fib(n) {
  if (n === 0 || n === 1) {
    return 1;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}

// 出力
console.log(fib(0)); // 1
console.log(fib(1)); // 1
console.log(fib(2)); // 2
console.log(fib(3)); // 3
console.log(fib(4)); // 5
console.log(fib(50)); // stackoverflow
```

> スタックオーバーフロー ≒ メモリ不足。コールスタックを超えていった

## Student

```ts
const fib = (n: number): number => (n <= 1 ? n : fib(n - 1) + fib(n - 2));

console.log("fib:", fib(50)); // stackoverflow
```

## Expert

```ts
  const memoFib = (n: number) => {
    const memo = new Map();
    memo.set(0, 0);
    memo.set(1, 1);
    const fib_ = (n: number) => {
      if (memo.has(n)) {
        return memo.get(n);
      }
      const result: number = fib_(n - 1) + fib_(n - 2);
      memo.set(n, result);
      return result;
    };
    return fib_(n);
  };

  console.log(memoFib(50)); // 👌
```

## 学び

- __参照透過性__: 入力(渡す値)が同じであれば、出力（戻り値）が同じであるという性質
- __副作用__: 関数とは引数を受け取り、値を返すものである。それ以外の振る舞いを副作用と名付けた。望まれない子か救世主か。それは、生みの親に委ねられた。子供に罪はないと人々は豪語する。
- __純粋関数__: 副作用のないピュアな関数 


JavaScript フィボナッチでスタックオーバーフローをちょっと観察

```js
const getLengthOfOptiomalCompression = function(str) {
  if (str.length === 0) {
    console.log('Please enter valid string.');
    return;
  }

  let output = '';
  let count = '';
  for (let i = 0; i < str.length; i++) {
    count++;
    if (str[i] !== str[i+1]) {
      output += str[i] + count;
      count = 0;
    }
  }
  console.log(output);
}

getLengthOfOptiomalCompression('aaaa');
getLengthOfOptiomalCompression('aaaabbccddd');

```

JavaScript Run-length encoding

```js
let lastElement = array.slice(-1)[0];
// or 
let lastElement = array[array.length - 1];
```

JavaScript 配列の最後の要素 取得

```js
// 予約リスト(APIから取得した想定)
const reservationList = [
  { startTime: new Date('2021-10-01 09:00:00'), endTime: new Date('2021-10-01 10:00:00') },
  { startTime: new Date('2021-10-01 10:00:00'), endTime: new Date('2021-10-01 11:00:00') },
  { startTime: new Date('2021-10-01 14:00:00'), endTime: new Date('2021-10-01 15:00:00') },
];

/**
 * 予約可能かを判定して返す
 * 予約リストにレコードがない場合は、予約できる true
 * 予約リストにレコードがある場合は、予約できない false
 * @param {Object} params
 * @param {Date} params.startTime - 予約の開始時間
 * @param {Date} params.endTime - 予約の終了時間
 * @returns {boolean}
 */
function searchReservation(params) {
  const { startTime, endTime } = params;

  let canReserve = true;
  for (reservation of reservationList) {
    // 予約可能な条件の逆の場合、予約できないフラグを立てる
    if (!((reservation.endTime <= startTime) || (endTime <= reservation.startTime))) {
      canReserve = false;
      break; // falseになった場合、ループを終了する
    };
  }
  return canReserve;
};

// 実行
// 予約が埋まっていない場合、true
console.log(searchReservation({
  startTime: new Date('2021-10-01 11:00:00'),
  endTime: new Date('2021-10-01 12:00:00')
})); // true

// 予約が埋まっている場合、false
console.log(searchReservation({
  startTime: new Date('2021-10-01 09:00:00'),
  endTime: new Date('2021-10-01 10:00:00')
})); // false
```

JavaScript カレンダー予約の重複チェック

```js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let newNum = [...nums1, ...nums2];
    newNum.sort(function(a, b) {
      return a - b;
    });
    console.log("newNum:", newNum);
    let half = (newNum.length / 2) | 0;
    console.log("half:", half);
    if (newNum.length % 2) {
        return newNum[half]
    }
    return (newNum[half-1] + newNum[half]) / 2;
};
```