[TIL] JS - 재귀 심화

Today I Learned

Memoization

• JS에서 재귀 함수가 호출될 때마다 stack에 쌓이기 때문에 처리 시간이 오래 걸릴 수 있고 한번에 너무 많은 호출이 반환되지 않고 쌓이면 stack overflow가 일어날 수도 있다.
• Memoization을 이용하면 호출 결과값들이 저장되어 불필요한 중복 호출을 줄일 수 있다는 장점이 있다.

예시 : 피보나치

function fibonacci(num, memo) {
  memo = memo || {};
  if (num < 2) return num;
  if (num in memo) return memo[num];
  memo[num] = fibonacci(num - 2, memo) + fibonacci(num - 1, memo);
  return memo[num];
};

Tail Call Optimization

// What is tail call?
function foo(x) {
  return bar(x); // tail call
}

function bar(x) {
  return x-1;
}

function baz(x) {
  return baz(x-1); // recursive tail call
}

• TCO를 지원하는 엔진에서는 tail call이 끝나면 이를 담고 있는 함수 또한 끝난다는 것을 인지하고 새로운 스택 프레임을 만들지 않고 이미 존재하는 스택 프레임을 사용한다. 따라서 TCO되지 않은 경우보다 빠르고 메모리도 적게 사용한다. (모든 브라우저에서 지원하지는 않고 현재 지원하는 브라우저는 Safari뿐이다.)
• TCO된 재귀함수 사용시 base case에 도달하는 즉시 전체의 결과값을 알수 있다.

예시 : 팩토리얼

// Naive Facotiral
function factorial(num) {
  if (num <= 1) return 1;
  return num * factorial(num-1);
}

// TCO Factorial
function factorial(num, acc) {
  // acc에 결과값을 누적시켜 전달
  acc = acc || 1;
  if (num <= 1) return acc;
  return factorial(num-1, num*acc);
}

JSON.stringify()

• JSON (JavaScript Object Notation)은 경량의 데이터 교환 형식으로 JS에서 파생되어 JS와 유사한 형식을 가지지만 언어로부터 독립적이다.주로 비동기 브라우저/서버 통신을 위해 사용된다.
• JS에는 값이나 객체를 JSON 문자열로 (JSON.stringify()), 반대로 JSON 문자열을 값이나 객체로 (JSON.parse()) 변환시켜주는 내장 메서드가 있다.
• JSON은 key: value 형식으로 포맷이 정해져 있으며 항상 ""으로 묶어서 사용한다.
• 모든 데이터타입을 JSON으로 파싱할 수 있는 것은 아니다. function과 undefined는 파싱할 수 없다.

JSON.stringify()를 재귀함수 로 구현하기

function stringifyJSON(obj) {
  // 1. Number
  if (typeof obj === "number") {
    return `${obj}`;
  }
  // 2. Boolean
  if (typeof obj === "boolean") {
    return `${obj}`;
  }
  // 3. String
  if (typeof obj === "string") {
    return `"${obj}"`;
  }
  // 4. Null
  if (obj === null) {
    return `${obj}`;
  }
  // 5. Array
  if (Array.isArray(obj)) {
    // if the array is empty
    if (obj.length === 0) return `[]`;

    const result = [];
    for (let el of obj) {
      result.push(stringifyJSON(el));
    }
    return `[${result.join(",")}]`;
  }
  // 6. Object
  if (typeof obj === "object") {
    // if the object is empty
    if (Object.keys(obj).length === 0) return `{}`;

    const result = [];
    for (let key in obj) {
      // if the type of value is function && not undefined
      if (typeof obj[key] !== "function" && obj[key] !== undefined) {
        const str = `"${key}":${stringifyJSON(obj[key])}`;
        result.push(str);
      }
    }
    return `{${result.join(",")}}`;
  } 
};