What is Recursion? (재귀함수)

1. 알고리즘과 복잡도 (재귀)

데이터 구조에 대한 이해를 하려면 재귀나 복잡성 등을 이해해야 한다고 한다. 중간중간 재귀적으로 사고하기, 잘게 쪼개어 사고한다 라는게 무엇을 의미하는 걸까?

다르게 그리고 다양하게 생각하는 능력을 기르기 위해서 배우는 것이라 한다.

2. 재귀

이런 문제가 주어졌다고 하자.

문제 : 자연수의 리스트를 입력으로 받아 리스트의 합을 리턴하는 함수 ‘arrSum’ 을 작성하세요.

그럼 보통 여기서 그동안 학습한 대로 초기값과 반복문을 적용한 함수를 만든다.

function arrSum(...nums) {
  let sum = 0 // 1. 보조 변수 sum 을 0 으로 초기화 한다.
  for (let i = 0; i < nums.length; i++) {
    sum = sum + nums[i] // 2. 순차적으로 리스트의 구성요소에 접근하면서 sum 에 더한다.
  }
  return sum
}

예로 자연수의 리스트 [10, 3, 6, 2] 의 합을 구한다고 가정하면,

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

1. 원래의 문제에서 출발하여 더 작은 경우를 생각한다.
2. 계속해서 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각한다.
3. 이렇게 문제 풀기를 미루다가 문제가 간단해져서 바로 풀 수 있게 되는 순간에 미뤄왔던 문제들을 차근차근 해결한다.

이처럼 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀 (recursion) 라고 한다.

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

arrSum 을 첫번째로,

1. arr 이 빈 배열인 경우 = 0
2. 그 외의 경우, arr[0] + arrSum(arr2) // arr2는 arr의 첫 요소를 제외한 나머지 배열

다시 한번 더 정의를 적어보면, arrSum 의 인자가 빈 배열이 들어오는 경우를 제외하면 실행과정 중에 자기 자신을 호출하기도 한다. 이러한 호출 방식을 재귀 호출이라고 한다.

3. 재귀는 언제 사용하는 게 좋은가?

1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도 (number of loops) 를 미리 알 수 없는 경우

사실 모든 재귀 함수는 재귀호출 없이 while / for loop 으로 표현이 가능하다.

하지만 재귀를 사용 가능한 경우, 재귀를 사용한 코드가 대부분의 경우 더욱 간결하고, 일부의 경우에는 이해하기도 쉽다고 한다.

4. 재귀적 사고의 흐름

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

재귀함수를 통해 어떤 문제를 풀고자 하는지, 문제를 가장 추상적으로, 또는 가장 단순하게 정리한다.

arrSum: [number] => number

arrSum? 그거 number 타입을 요소로 갖는 배열을 받아서 number 를 리턴하는거?

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

주어진 문제를 어떻게 쪼갤 것인지 고민해 보기. 어떤 기준을 (일반적으로 입력값) 정하고 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 검토해 본다.

가령 입력값에 따라 입력값이 빈 배열일 때 혹은 그렇지 않을 때로 구분하는 것처럼 말이다.

문제를 쪼갤 때 중요한 관점은 순서, 그리고 크기 이다.

2-1. 주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나,

2-2. 순서를 명확하게 정할 수 있는지

그리고 그렇게 구분되어진 문제들을 푸는 방식이 같다면 문제를 제대로 구분한 것이다.

3. 단순한 문제 해결하기

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

arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열인 경우이고, 이 때 arrSum 은 0 이다.

4. 복잡한 문제 해결하기

위의 예로 arrSum 이 길이가 1이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고 나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head 에 더한다.

arrSum: [number] => number
arrSum([]) = 0
arrSum([e1, e2, ..., en]) = e1 + arrSum([e2, ..., en])

배열이 있을 때 head 와 나머지부분 (tail) 을 구분하는 방법만 안다면 arrSum 을 해결할 수 있다.

5. 코드 구현하기

function arrSum(arr) {
  if (arr.length === 0) {
    // 재귀의 기초 (base case)
    return 0 // 문제를 더 이상 쪼갤 수 없을 때 단순한 문제의 해답을 리턴
  }
  return head + arrSum(tail) // 더 작은 문제로 새롭게 정의된 문제 (recursive case)
}

5. 문제를 풀어보고 느낀 점

계속 연습을 해야 자전거 타듯이 익숙해 질 것이라 생각한다.