재귀함수의 두 가지 조건

1. 재귀 종료 조건
2. 매번 다른 데이터를 통해 함수 호출

// 재귀
const countDown = (num) => {
  if (num <=0) { // 종료 조건
    console.log("All done!");
    return;
  }
  console.log(num);
  num--;
  countDown(num); // 매번 다른 num을 통해 호출
}

// 일반
const contDown2 = (num) => {
  for (let i = num; i > 0; i--) {
    console.log(i);
  }
  console.log("All done!");
}
countDown(5);

// 재귀
function sumRange(num) {
    if(num === 1) return 1;
    return num + sumRange (num - 1);
}
// 3을 넣으면
1. 3 + sumRange(2)
2. 3 + 2 + sumRange(1)
3. 3 + 2 + 1

재귀로 팩토리얼 구현하기

function factorial(num) {
    if (num === 1) return 1;
    return num * factorial(num - 1);
}

재귀의 잠재 위험성

재귀함수를 구현할 때, 종료조건 미 설정, 값 반환하지 않음, 잘못된 값 반환을 할 경우 스택오버플로우가 난다. 따라서 이 두 가지 조건을 제대로 확인 한 후 구현해야한다.

helper method 재귀

배열이나 데이터 목록 등을 컴파일 해야할 때 흔히 이렇게 작업한다.

// 기본 형태
function outer(input) {
    let outerScopedVariable = [];

    function helper(helperInput) { // 재귀 함수
        helper(helperInput--);
    }

    helper(input);

    return outerScopedVariable;
}

가령 배열에서 모든 홀수값을 수집하는 등의 작업을 할 때 사용하면 유용하다.

function collectOddvalues(arr) {
    let res = [];

    function helper(helperInput) { // 재귀 함수
        if (helperInput.length === 0) return;
        if (helperInput[0] % 2 !== 0) res.push(helperInput[0]);
        helper(helperInput.slice(1));
    }

    helper(arr);

    return res;
}

이렇게 하면 함수가 호출 된 이후에도 res가 유지될 수 있다.

순수 재귀

위의 collectOddvalues를 순수 재귀로 구현하면 아래와 같다.

function collectOddvalues(arr) {
    let newArr = [];

    if (arr.length === 0) return newArr;
    if (arr[0] % 2 !== 0) newArr.push(arr[0]);
    newArr = newArr.concat(collectOddvalues(arr.slice(1)));
  //newArr = [...newArr, ...collectOddvalues(arr.slice(1))]; // 이렇게도 가능하다.
    return newArr;
}

collectOddvalues([1, 2, 3, 4, 5]);
// 1. [1].concat(collectOddvalues([2, 3, 4, 5])) => [1, 3, 5]
// 2. 	[].concat(collectOddvalues[3, 4, 5]) => [3, 5]
// 3. 		[3].concat(collectOddvalues[4, 5]) => [3, 5]
// 4. 			[].concat(collectOddvalues[5]) => [5]
// 5. 				[5].concat(collectOddvalues[]) => [5]
// 6.					[]

순수 재귀를 사용할 때는 배열을 복사하는 slice, spread, concat등의 method를 사용하고, 문자열도 마찬가지로 slice나 substring을 사용하여 사본을 만들어야 한다. 객체의 경우는 Object.assign혹은 spread연산자를 사용하는 게 유용하다.

순수 재귀가 더 짧게 작성할 수 있으나 보통은 helper method재귀가 이해하기 용이하며 가독성이 좋다.

재귀활용

// 재귀를 통한 json.stringify구현
function stringifyJSON(obj) {
  // your code goes here
  const isBaseCase = (obj) => {
    if (typeof obj === "string") return `"${obj}"`;
    if (typeof obj === "number" || !obj || obj === true) return `${obj}`;
    if (Array.isArray(obj)) if (obj.length === 0) return "[]";
    if (Object.keys(obj).length === 0) return "{}";
    return false;
  };

  if (isBaseCase(obj)) return isBaseCase(obj);

  // Recursive case
  return Array.isArray(obj)
    ? `[${obj.map((el) => stringifyJSON(el))}]`
    : `{${Object.keys(obj)
        .filter((el) => typeof obj[el] !== "undefined")
        .filter((el) => typeof obj[el] !== "function")
        .map((el) => `${stringifyJSON(el)}:${stringifyJSON(obj[el])}`)}}`;
}

// 재귀를 통한 treeUI구현
function createTreeView(menu, currentNode) {
  for (const el of menu) {
    const li = document.createElement("li");
    if (el.children) {
      const input = document.createElement("input");
      input.type = "checkbox";

      const span = document.createElement("span");
      span.textContent = el.name;

      const ul = document.createElement("ul");
      li.append(input, span, ul);
      currentNode.append(li);

      createTreeView(el.children, ul);
    } else {
      li.textContent = el.name;
      currentNode.append(li);
    }
  }
}