TIL22, 재귀

컴공과 학생이 교수님에게
‘교수님, 재귀란 무엇인가요?’
라고 물었더니, 교수님이 말씀하시기를

‘아주 옛날 산꼭대기에 세상의 모든 지식을 통달한 도인이 살았는데,
세상 사람들이 찾아와 지식을 얻어가곤 했다네.
어느날 한 사람이 찾아와 그 도인에게 ‘재귀란 무엇인가요?’ 라고 물었더니
도인이 하는말이, ‘아주 옛날 산꼭대기에 세상의 모든 지식을…’

재귀가 무엇인지 물을때 자주 나오곤 하는 클리셰인듯 하다.
개인적으로 재귀를 재밌게 표현한 좋은 이야기 같다.
그렇다면 진짜 ‘재귀’란 무엇일까?
사실 이름부터 어렵다. 재귀..

재귀

재귀란, 어떤 문제를 해결할 때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법이다.
반복문과 비슷한데, 이 둘은 차이점이 있다.

반복문은 메모리를 덜 차지하기 때문에 실행속도가 빠르지만, 가독성이 다소 떨어진다.

재귀는 메모리를 차지하기 때문에 실행속도가 느리지만, 코드가 짧고 가독성이 좋다.

그렇다면 재귀는 언제 사용하는것일까?

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우.

const arr = [1, 2, 3, 4];
위와 같은 배열의 모든 합인 arrAdd를 구하고자 할 때,
arrAdd([1, 2, 3, 4]) = 1 + arrAdd([2, 3, 4])와 같다고 볼 수 있다. 이걸 더 쪼개면,
arrAdd([2, 3, 4]) = 2 + arrAdd([3, 4])와 같다고 볼 수 있다. 이걸 더 쪼개면,
arrAdd([3, 4]) = 3 + arrAdd([4])와 같다고 볼 수 있다. 이걸 더 쪼개면,
arrAdd([4]) = 4 + arrAdd([])와 같다고 볼 수 있다. 이걸 더 쪼개면,
arrAdd([]) = 0 이라고 할 수 있다.

결국 더이상 쪼갤 수 없는 상황 (여기선 0이 됐다)부터 앞서 생성한 문제를 해결한다.
arrAdd([4]) = 4 + arrAdd([]) = 4;
arrAdd([3, 4]) = 3 + arrAdd([4]) = 3 + 4 = 7;
arrAdd([2, 3, 4]) = 2 + arrAdd([3, 4]) = 3 + 4 + 2 = 9;
arrAdd([1, 2, 3, 4]) = 1 + arrAdd([2, 3, 4]) = 3 + 4 + 2 + 1 = 10;

1. 중첩된 반복문이 많거나, 반복문의 중첩 횟수를 예측하기 어려운 경우.

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    for (let k = 0; k < n; k++) {
      for (let l = 0; l < n; l++) {
        for (let m = 0; m < n; m++) {
          for (let n = 0; n < n; n++) {
            for (let o = 0; o < n; o++) {
              func(i, j, k, l, m, n, o);
            }
          }
        }
      }
    }
  }
}

이런 경우 반복문 안에서 재귀를 실행시켜 반복문 중첩을 없앨 수 있다.

그럼, 재귀를 어떻게 사용하면 좋을까?

재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기
   • 재귀적으로 사고할 때 가장 먼저 해야할 일은 문제를 가장 추상적으로, 또는 가장 단순하게 정의하는 것이다.
   • 함수 arrAdd는 number 타입을 요소로 갖는 배열을 입력받고, number 타입을 리턴한다.
   • arrAdd: [number] ⇒ number로 나타낼 수 있다.
2. 문제를 쪼개고 경우의 수를 나누기
   • 일반적으로 문제를 더이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나뉜다.
   • arrAdd: [number] ⇒ number
   • arrAdd([]) → 문제를 더이상 쪼갤 수 없는 경우
   • arrAdd([el1, el2, … eln]) → 그렇지 않은 경우
3. 단순한 문제 해결하기
   • 여러 경우의 수로 나눈 뒤에는 가장 해결하기 쉬운 문제부터 해결한다.
   • 이를 재귀의 기초(Base Case)라고 한다.
   • arrAdd를 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열인 경우이고, 리턴값은 0이다.
   • arrAdd: [number] ⇒ number
   • arrAdd([]) = 0 → 문제를 더이상 쪼갤 수 없는 경우. Base Case
   • arrAdd([el1, el2, … eln]) → 그렇지 않은 경우
4. 복잡한 문제 해결하기
   • Base Case를 해결했다면, 남아있는 복잡한 문제를 해결한다.
   • 길이가 1 이상인 배열이 arrAdd에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고(head), 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결해 얻은 결과를 head에 더한다.
   • arrAdd: [number] ⇒ number
   • arrAdd([]) = 0 → Base Case를 해결했다.
   • arrAdd([el1, el2, … eln]) = el1 + arrAdd([el2, … eln]) → 맨 앞의 요소인 head를 el1으로 지정, head를 제외한 나머지 요소들을 자기 자신 함수로 다시 호출한 뒤 head에 더해준다.