[JavaScript memoization] 피보나치 수열 재귀함수

memoization이란?

메모이제이션은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. -위키백과

반복문을 사용하지 않고, 재귀함수로만 피보나치 수열의 n번째 항의 수를 리턴하는 함수 구현하기

function fibonacci(n) {
  const memo = [0, 1]; //const로 선언
  const aux = (n) => { //재귀함수 aux. memo배열을 조회하고, 값을 저장하는 역할
    
    //memo 배열 안에 해당 값이 있는지를 먼저 조회 = 최적화
    if (memo[n] !== undefined) { 
      return memo[n]; //피보나치(5)면 5번째 숫자를 return한다.
    } 
    
    //memo 배열 안에 해당 값이 없는 경우
    else {
      memo[n] = aux(n - 1) + aux(n - 2);
    }
    
    //피보나치(5)는 aux(4) + aux(3)을 조회하고 aux(4)는 다시 aux(3)과 aux(2)를 조회하고...
    //결국 memo안에 가지고 있는 요소를 찾아와서 활용하여 aux(2), aux(3) ... 을 순서대로 memo배열에 저장하는 것
    
    return memo[n]; //memo배열의 n번째 인덱스 값이 aux함수의 return 값이 되는 것
  };
  
  return aux(n);
};