[TIL]JS-再回帰深化

Today I Learned

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
}

例:ファクトリ

// 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.再帰関数で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(",")}}`;
  } 
};