helper함수를 이용한 보다 쉬운 재귀

helper

• 알고리즘, 코딩테스트에서 많이 사용하는 재귀함수에 좀 더 쉽게 접근할 수 있다.

• 위의 leetcode를 예로 들면, function내에 helper라는 이름을 가진 함수를 두고, 이를 내부에서 재귀처리하는 방식

• 이 helper를 이용한 이점이 몇가지가 있는데,

  • 코드가 깔끔해진다.
  • 재귀함수 내에서 사용하는 변수를 바깥scope에 둬도 가능하지만, 잘못하면 버그가 발생할 수 있고, 불필요한 메모리 사용. 처음 봤을 때 함수 내에서만 사용하는지 어떤지를 알 수 없다.
  • 재귀함수가 계속 처리되어도 디버깅이 쉬워진다.

Merge sort

보다 더 쉬운 이해를 위하여 Merge sort에 적용해본다면...

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  let merged = [];
  let lIndex = 0;
  let rIndex = 0;

  while (lIndex < left.length && rIndex < right.length) {
    if (left[lIndex] < right[rIndex]) {
      merged.push(left[lIndex++]);
    } else {
      merged.push(right[rIndex++]);
    }
  }
  while (lIndex < left.length) {
    merged.push(left[lIndex++]);
  }

  while (rIndex < right.length) {
    merged.push(right[rIndex++]);
  }
  return merged;
}

위처럼 구현 할 수가 있을텐데, 여기서 merge는 이해하기 어렵지 않으나 mergeSort내에서 자꾸 재귀호출을 하는게 여간 신경쓰이지 않을 수 없다.
뭐 혼자 도는거 같은데, 이걸 어찌 도는지.. 몇번 호출하는지, 호출 후 어찌되는지...

Helper를 적용한 Merge sort

function mergeSort(arr) {
  let result = [];

  function helper(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = helper(arr.slice(0, mid));
    const right = helper(arr.slice(mid));

    if (left && right) {
      result.push(...merge(left, right));
    }

    return;
  }
  helper(arr);
  return result;
}

function merge(left, right) {
  let merged = [];
  let lIndex = 0;
  let rIndex = 0;

  while (lIndex < left.length && rIndex < right.length) {
    if (left[lIndex] < right[rIndex]) {
      merged.push(left[lIndex++]);
    } else {
      merged.push(right[rIndex++]);
    }
  }
  while (lIndex < left.length) {
    merged.push(left[lIndex++]);
  }

  while (rIndex < right.length) {
    merged.push(right[rIndex++]);
  }
  return merged;
}

재귀야 어찌되던, 이제는 result라는 변수만 잘 추적하면 잘 알 수 있다.

• 디버깅이 훨씬 수월해진다.
• 재귀함수로 정상적인 기대값이 발생하지 않아 확인을 하려 할 때에는 스택에 함수들이 쌓여가고, 재귀함수가 호출될때마다 함수안의 변수들의 값이 갱신되버린다.
• 즉, 뭐좀 보려고 하면 또 호출되면서 기존값들 확인이 힘든것이 문제인데
• 위처럼 작성한다면 재귀함수의 callstack이 종료되어도 result변수는 계속 존재하기 때문에 집중하여 쉽게 확인이 가능하다는 장점이 있다.