JS/알고리즘 재귀 알고리즘(recursive algorithms)

 

 

• 학습 내용

이번 학습할 내용은 알고리즘의 기초 첫 번째 재귀이다. 재귀란 어떤 문제에 있어서 그 문제를 동일한 구조의 더 작은 문제로 나눌 수 있고 이 작은 문제를 해결하여 전체 문제를 푸는 방법이다. 알고리즘을 해결하는 것에 있어 재귀가 매우 많이 사용된다. 이번부터 학습할 알고리즘은 자바스크립트의 문법적인 요소보다는 문제를 해결하는 방법이라고 할 수 있다. 그렇기에 아주 폭넓고 쉽지 않은 개념이다. 지금부터 시작해서 천천히 조금씩 하나하나 학습해보고자 한다. 그래서 이번 시간에 재귀적으로 사고하는 법과 재귀 함수의 활용 방법에 대해 간단히 살펴볼 것이다.

 

• 문제를 쪼개어 생각하는 방법

재귀로 문제를 해결할 때는 먼저 기존의 문제에서 출발하여 더 작은 경우를 생각해야 한다. 예를 들면 이렇다.

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2])

이렇게 한번 쪼개고 다시 문제를 살핀다. 그리고 더 쪼개질 수 있는가를 살펴본다. 이문제의 경우 더 쪼개질 수 있다는 것을 알 수 있다.

arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);

문제가 이렇게 더 이상 쪼개지지 않게 되면 이제 간단한 문제부터 생성된 문제를 하나씩 해결한다.

arrSum([]) = 0 // 더 이상 작게 접근할 수 없는 경우
arrSum([2]) = 2 + arrSum([]); = 2;
arrSum([6, 2]) = 6 + arrSum([2]); = 6 + 2 = 8
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]); = 3 + 8 = 11
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]); = 10 + 11 = 21

이렇게 문제를 해결하는 것이 재귀적으로 문제를 해결하는 것이다. 이 것을 함수화하면 이렇게 표현할 수 있다.

function arrSum(arr) {
  if (arr.length === 0) {
    return 0;
  } else {
    return arr[0] + arrSum(arr.slice(1));
  }
}
arrSum([10,3,6,2]) // 21

이렇게 실행 과정 중에 자기 자신을 호출하는 것을 재귀 호출이라고 한다.

 

• 재귀에 적합한 상황

재귀에 적합한 상황으로 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우이거나 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우에 적합하다. 예를 들어 들어오는 전달 인자에 개수가 미지수인 경우 반복을 미리 정하기 어렵다. 이 경우 이렇게 사용할 수 있다.

function flattenArr(arr) {
  let result = [];
  for (let el of arr) {
    if (Array.isArray(el)) {
      result.push(...flattenArr(el))
    } else {
      result.push(el)
    }
  }
  return result;
}

 

• 재귀적으로 사고하는 방법

첫째, 재귀적으로 사고하기 위해서 가장 먼저 해야 할 일은 문제를 추상적이거나 가장 단순하게 정의하는 것이다. 그리고 둘째로 주어진 문제를 어떻게 조갤 것인지 고민한다. 문제를 쪼갤 기준을 정하고, 기준에 따라 문제의 큰 경우와 작은 경우로 구분하여 해결한다. 셋째, 문제를 여러 경우로 구분한 다음 해결하기 가장 쉬운 것부터 해결한다. 이 것을 재귀의 기초(base case)라고 한다. 이 것이 재귀의 탈출 조건이 된다. 마지막으로 순서대로 남아있는 복잡한 문제를 해결한다.

function recursive(input1, input2, ...) {
  //Base Case
  if (문제를 더 이상 쪼갤 수 없는 경우) {
    return 가장 단순한 문제 답
  }
  // recursive Case
  else {
    더 작은 문제로 새롭게 정의된 문제
  }
}

 

• 느낀 점

이번 시간에 학습한 재귀 알고리즘의 경우 개념은 그리 복잡하지도 방대하지도 않지만 이것을 이해하고 숙련하는 것에 아주 애를 먹었다. 기존에 가지지 못한 접근 방법의 사고여서 그 사고를 학습하기 위해 많은 문제를 풀어야 했다. 그래서 많은 시간을 할애하게 된 파트이다. 물론 아직 부족한 부분이 많고, 더 많은 문제를 풀어야 한다고 느꼈다. 특히 알고리즘 즉, 문제를 해결하는 사고를 학습하는 것에 있어서는 물론 저렇게 내 머리가 알아서 창의적으로 굴러가면 좋겠지만 나에게는 무리였기에 많은 문제를 풀고 더 좋은 케이스를 많이 보는 게 중요하다고 느꼈다. 예를 들면 수학 문제를 많이 푸는 이유와 유사하다. 수학의 고차원적인 문제들에 있어 해결하기 위해 접근해야 하는 방법이 아주 방대하고 까다로운 경우가 아주 많다. 그래서 많은 케이스를 접하면서 그 해결 방법으로 접근하는 사고를 학습한다. 이 알고리즘이 이 경우에 가깝다고 볼 수 있다. 그래서 앞으로 학습해야 할 알고리즘이 정말 많은데 이러한 방향을 가지고 지속적으로 학습해보고자 한다.