재귀적 사고 연습하기

누군가는 재귀를 자전거를 타는 것에 비유하기도 합니다. 다른 사람이 타는 것을 옆에서 지켜보면 꽤 쉬워 보이는데 막상 내가 타려고 하면 생각보다 잘 안 됩니다. 자전거를 잘 타는 방법은 계속 시도하고 연습하는 수밖에 없습니다. 재귀 역시 마찬가지입니다. 자연스러워질 때까지 연습해야 합니다.

Guide : 재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기

재귀 함수를 통해 어떤 문제를 풀고자 하는 지, 즉 우리의 목표를 정리하는 데 도움이 됩니다. 문제를 가장 추상적으로 또는 가장 단순하게 정리하는 것입니다. arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받아서 number를 리턴합니다. 이를 좀더 간편하게 아래와 같이 표기한다고 가정합시다.

• arrSum: [number] => number

2. 문제를 쪼개고 경우의 수를 나누기

주어진 문제를 어떻게 쪼갤 것인지 고민합니다. 어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 검토해봅니다. 일반적으로 입력값이 이 기준을 정하는 대상이 됩니다. 이 때 중요한 관점은 순서와 크기입니다. 주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나, 순서를 명확하게 정할 수 있는지를 살펴보는 것이 도움이 됩니다. 그리고 구분된 문제들을 푸는 방식이 같다면, 문제를 제대로 구분한 것입니다.

• arrSum의 경우 입력값인 배열을 크기에 따라 구분할 수 있습니다. 그리고 arrSum([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])을 구하는 방법은 동일할 것이므로 이 구분은 적절하다고 판단할 수 있습니다.

  이제 문제의 입력값에 따라 경우의 수를 나눕니다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눕니다.

• arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 각각의 경우는 다르게 처리되어야 합니다.

• arrSum: [number] => numberarrSum()arrSum([e1, e2, ... , en])

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)이라고 부릅니다. 재귀의 기초는 나중에 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게 됩니다.

• arrSum를 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이 때 arrSum은 0입니다.
• arrSum: [number] => numberarrSum() = 0arrSum([e1, e2, ... , en])

4. 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결합니다.

• arrSum이 길이가 1 이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이겠습니다.), 나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더합니다.
• arrSum: [number] => numberarrSum() = 0arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])
• 배열이 있을 때 head와 나머지 부분(tail)을 구분하는 방법만 안다면, arrSum을 해결할 수 있습니다.

5. 코드 구현하기

function arrSum(arr) {
// 재귀의 기초 (base case)
// 문제를 더 이상 쪼갤 수 없을 경우
if (arr의 길이가 0인 경우) {
    return 0;
}
// recursive Case
// 그렇지 않은 경우
// head: 배열의 첫 요소
// tail: 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}

아래는 일반적인 재귀 함수의 템플릿입니다.

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}