Recursion

아래 함수 simpleRecusion 내부에서 자기 자신을 호출하고 있는데, 이것을 재귀호출이라고 합니다. 하지만 아래 함수는 심각한 문제가 있습니다. 영원히 끝나지 않는다는 것이죠.

fun simpleRecusion() {// 재귀는 맞지만 잘못된 재귀함수
  simpleRecusion()
}

지금부터 재귀가 왜 필요한지, 재귀 사용시 주의할점 그리고 어떤 경우에 사용하는지를 살펴보려고 합니다.

$$N! = N \times (N - 1) \times ... \times 2 \times 1$$

팩토리얼입니다. 해결해야 하는 팩토리얼 문제가 생겼다고 가정해볼게요. 여기서 핵심은 divide & conquer, 분할정복입니다. 분할정복은 크고 복잡한 문제를 작고 쉬운 문제로 쪼개어 해결하려는 것인데, 실제로 재귀는 분할정복 중 하나입니다.

그럼 위 팩토리얼을 어떻게 작고 쉬운 문제로 쪼갤까요? 위 식은 제일 큰 수인 N과 (N-1) X (N-2) X ... X 2 X 1 의 곱이라고 생각할 수 있습니다. 즉, N! = N X (N−1)! 인거죠. 이 때 , N! 이라는 문제 안에 하나 작은 문제인 (N-1)! 가 있다는 것이 포인트입니다. 이렇게 같은 성격의 작은(혹은 같은) 문제를 subproblems, mirror images라고 하고, 이렇게 어떤 문제 안에 자기 자신과 같은 성격의 문제들이 있는 구조를 Recursive Structure, 재귀적 구조라고 합니다. 이제 팩토리얼의 재귀적 구조에 대한 규칙을 파악함으로 굳이 숫자를 나열할 필요가 없어졌습니다.

아직 (N-1)! 은 크기 때문에, 계속해서 문제를 작게 쪼개어 가장 작은 문제를 찾아 보겠습니다. 1은 아니죠. 이미 아시겠지만, 1! = 1 = 1 X (1−1)! = 1 X 0! 이기 때문에 0! 이 가장 작은 문제고, 0이 가장 작은 케이스가 됩니다. 이렇게 문제를 더 작은 문제로 쪼갤 수 혹은 쪼갤 필요가 없는 케이스를 Base case라고 합니다. 굳이 계산할 필요없이 바로 답을 알 수 있는 기본이 되는 케이스입니다. 이 베이스 케이스가 왜 중요한지는 재귀 문제를 해결하기 위한 step과 함께 살펴보겠습니다.

재귀 문제를 풀기 위한 steps

문제를 파악한다. 모든 문제 푸는 것의 가장 기초가 되는 부분이죠. N!을 예시로 들면, N보다 크지 않고, 1보다 작지 않은 자연수들을 전부 곱하는 것입니다.
original 문제에서 하나 작은 문제를 찾아라. 즉, 재귀적인 구조를 찾아야 합니다. 재귀 문제를 다루기 위해 가장 중요한 부분으로 아까 앞에서 다뤘던 부분이죠.
Base Case를 찾아라. Termination condition 종료조건이기 때문이죠. 가장 조심해야하는 부분입니다.

3번을 좀 더 자세히 보겠습니다. 아래는 팩토리얼 구현인데, 문제가 있습니다.

fun factorial(n: Int): Int {//잘못된 재귀함수
  return n * factorial(n - 1)
}

return 3 * factorial(2)
return 2 * factorial(1)
return 1 * factorial(0)
return 0 * factorial(-1) => ?
return -1 * factorial(-2)
...

제가 5번까지 적었는데 이 재귀함수는 영원히 끝나지 않게 됩니다. 그 이유는 베이스 케이스 0에서 끝나지 않아서 입니다. 그래서 우리는 베이스 케이스에 도달하게 되면 재귀로직을 멈출 수 있게, termination condition_{종료 조건}을 추가해야 합니다. 즉, 베이스케이스가 argument로 들어오게 되면 재귀호출을 하지 않고 바로 값을 반환해주면 되겠죠?

바르게 고쳐보자

fun factorial(n: Int): Int {
  return if (n == 0) 1 
         else n * factorial(n - 1);
}

argument에 음수가 들어오지 않을 거라고 생각하고 작성한 코드인데, 항상 어떤 예외 상황이 발생할 수 있는지 고민하고, 그에 대한 적절한 예외 처리를 해주는 것은 매우 중요합니다. (즉, n이 음수라면, Exception을 일으키는 것이 좋겠죠?)

별로 중요한 건 아니지만 이런 식으로 함수 호출 수를 줄일 수도 있습니다. 그리고 아래 다른 버전으로 짜봤습니다.

fun factorial(n: Int): Int {
  if (n == 2) return 2;
  else if (n == 1 || n == 0) return 1;
  return n * factorial(n - 1);
}

fun factorial2(n: Int): Int {
   return when(n) {
        0,1 -> 1
        2 -> 2
        else -> n * factorial2(n - 1)
   }
}

주의점

재귀를 사용하면 간결하고 직관적으로 이해하기 쉬운 코드를 작성할 수 있고 non-recursive보다 더 효율적인 코드가 될 수 있습니다. 특히 트리나 그래프 탐색에서 자주 사용되는 접근법입니다.

하지만 재귀는 잘 고려하고 사용해야 합니다. 잘못 사용하면 오히려 독이기 때문에 정말 필요한지나 다른 문제는 없을지 신중히 생각해야 합니다. 기본적으로 재귀는 함수호출을 stack으로 쌓기 때문에 n이 너무 크다면 StackOverflowError가 발생할 수도 있고, non-recursive 코드보다 메모리도 더 많이 차지하게 될 수 있기 때문입니다.

자료구조) 1. Recursion

재귀는 무엇이고, 왜 사용하고, 어떻게 적용시키는지

Table of contents

Recursion

재귀 문제를 풀기 위한 steps

바르게 고쳐보자

주의점