Recursion

Recursion, 재귀. 재귀란 무엇일까? 우선 이해를 돕기 위해 아래의 코드를 보자.

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

simpleRecusion 함수 내부에 자기 자신을 호출하고 있다. 이것이 재귀다. 하지만 이걸로 재귀를 알았다고 하는 것은 정말 달을 못 보고 손가락 끝을 보고 있는 것이다. 우리가 지금 생각해야 하는 것은 재귀가 왜 필요한지, 어떤 경우에 사용하는지이다.

재귀를 사용하는 이유

재귀를 설명할 때, 제일 좋은 예시는 factorial이라고 생각한다. _{참고로 0!은 1이다.}

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

그리고 이렇게도 표현할 수 있다. 이 부분이 핵심이다. N!=N×(N−1)! 여기서 우리가 집중해야하는 포인트는 (N-1)!이다. 지금 여기서 이게 그냥 단순히 '당연한 거 아니야?'라고 넘겨버린다면 내 의도를 캐치하지 못하신 것 같다. 지금 N!라는 문제 안에 (N-1)!과 같이 똑같은 성격이지만 N보다는 하나 작은 문제가 있다는 것을 파악했다는 것은 이 문제를 Recursive Structure, 즉, 재귀적 구조로 파악을 했다는 것이다. (N-1)!도 역시 자신보다 하나 작은 문제로 이뤄져 있다는 것은 쉽게 알 수 있다. 딱 맞는 표현은 아닌 것 같지만 현재 상황을 이렇게 표현도 할 수 있을 것 같다. 팩토리얼의 재귀적인 구조에 대한 규칙을 파악하여 숫자를 나열할 필요가 없어진 것이다. 이쯤에서 재귀를 사용하는 이유에 대해 알아보자.

처음에 재귀가 무엇인가에 대해 말을 했는데, 한 함수 내부에서 자기자신을 호출하는 것이라고 말을 했다. 이건 어떻게 보면 구현 방법에 대한 설명이고, 우리가 좀 더 집중해야하는 것은 사실 이런 정의나 구현 방법보다, 이유라고 나는 생각한다. 재귀를 사용하는 이유가 무엇일까? 그냥 바로 말하자면, 재귀를 사용하는 이유는 어떤 복잡한 문제를 그 문제와 같은 성격의 작은 문제로 쪼개어서 보다 단순하고 쉽게 해결하기 위해서이다. 어? 그것은 분할정복법(divide and conquer)에 대한 설명 아닌가요? 라고 생각할 수 있는데, 맞는 말이다. 정확하게는 우리는 재귀를 구현함으로 분할정복법을 자연스럽게 사용하게 되는 것이고, 재귀만의 특징적인 부분은 지금 세번째 언급중인 함수가 자기자신을 참조(호출)을 하여 문제를 해결한다는 것이다.

재귀 문제를 풀기 위한 steps

1. 문제를 파악한다. 모든 문제 푸는 것의 가장 기초가 되는 부분이다. 문제가 무엇인지부터 제대로 파악해라. N!을 예시로 들면, N보다 크지 않고, 1보다 작지 않은 자연수들을 전부 곱하는 것이다.

2. original 문제에서 하나 작은 문제를 찾아라. 즉, 재귀적인 구조를 찾아라. 재귀 문제를 다루기 위해 가장 중요한 부분이다. N! = N * (N-1)! 아까 앞에서 다뤘던 부분이다.

3. Base Case를 찾아라. 가장 조심해야하는 부분이다.

Base Case을 나중에 설명하기로 하고, 우선 팩토리얼을 코드로 구현해보자.

function factorial(n) {
  return n * factorial(n - 1);
}

너무 어이없게 간단하지 않은가? 이래서 2번째 재귀적인 구조를 찾는 단계가 중요하다고 한 것이다. 우리는 그 문제의 구조를 파악함으로 복잡한 문제를 훨씬 간단하게 바라볼 수 있게 된다. 하지만 지금 현재 위 함수와 맨 처음에 재귀가 무엇인가를 언급하며 예시로 보여줬던 함수 둘 모두 심각하고 치명적인 오류가 있다. 아마 대부분의 사람들이 Recursion을 공부하면서 통과의례처럼 꼭 한번씩은 겪어봤을 것이라고 장담하는, 손에 땀을 쥐는 상황이 벌어지게 되는데, 간단하게 factorial 함수 argument에 3을 넣었다고 가정하고 흐름을 따라가보자.

1. return 3 * factorial(2)

2. return 2 * factorial(1)

3. return 1 * factorial(0)

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

5. return -1 * factorial(-2) ...

과연 이 함수의 결과는? 결국 0을 곱하게 되었으니, 무조건 0이다.

절대 아니다. 여기서 우리는 **termination condition(종료 조건)**을 넣어주지 않았기 때문에 Never Ending function_{(이 말은 내가 지어낸 것으로 다른 곳에서 썼다가 창피당하지 않았으면 좋겠다)}으로 이 함수는 영원히 끝나지 않을 것이다. 강제로 프로그램을 종료시켜주는 방법밖에 없다. 이런 것 때문에 3번째 단계 base case를 찾으라고 한 것인데... 과연 base case가 무엇일까?

Base Case?

base case. base의 뜻은 '기본, 바탕, 기반...'이고 case는 알다시피 '경우, 사건...'라는 뜻이다. 그럼, 대충 여기서 직역을 해보자면, '기본이 되는 경우(케이스)'라고 할 수 있겠다. 그리고 앞서 종료 조건이랑 이 베이스케이스와 연관이 있다고 했으니.. 혹시 감이 살짝 오는가? 다시 팩토리얼로 예시를 들어보자. 우리는 이 팩토리얼의 재귀적 구조를 파악을 했다. 작은 문제로 쪼개어서 문제를 해결한다고 했는데, 우리는 이 문제를 얼마나, 어디까지 쪼개어야 하는걸까? 우리 구현의 욕구를 잠시 뒤로 미뤄두고 정말 순수 팩토리얼 문제만 생각해보자.

1!=1×(1−1)!;=1×0!;=1

1×0!=1 ∴0!=1 그럼 0!이 1인 것을 알았으니 한가지 상황을 가정해보자. 만약 우리가 만든 함수의 argument로 0이 들어온다면 어떻게 해야할까? 1을 반환해줘야 한다. 그럼 한가지 아까 했던 질문을 다시 해보겠다. 1!이 정말 제일 작은 문제일까? 1!=1×0! 이제 잠깐 Base Case가 무엇인지 얘기하고 팩토리얼 문제를 마저 해결해보자.

Base Case는 굳이 더 작은 문제로 쪼갤 필요가 없는 기본이 되는 케이스들을 말한다. 문제 해결 관점(정복분할)에서 보면 base case는 너무 쉬운 문제로 우리가 답을 바로 낼 수 있는 케이스들을 말한다. 그리고 아까 만들었던 무한으로 계속 돌아가는(결국 Stack Overflow까지 가게 될 것이다.) 팩토리얼 함수의 문제를 해결하려는 관점에서 보면, 계속 하나 작은 문제로 쪼개고 쪼개다가 최소한으로 우리가 직접해결해줘야하는 종점**(termination condition_{종료 조건})**이라고도 볼 수 있다. 즉, 베이스케이스가 인자로 들어온다면, 바로 직접 답을 반환해주어 재귀호출이 일어나지 않게 해야 한다.

다시 돌아와서, 팩토리얼의 베이스케이스는 뭘까? 우리가 해결해줘야 하는 마지막 문제는 0!이니, 베이스케이스는 0이다. 그럼 지금까지, 문제를 파악했고, 재귀적 구조를 찾았고 마지막으로 베이스케이스까지 찾았다.

바르게 고쳐보자

방금 내용을 적용하여 팩토리얼 함수에 부족한 부분을 채워넣어보자.

function factorial(n) {
  if (n == 0) return 1;
  return n * factorial(n - 1);
}

arguments로 음수가 들어오지 않을 것이라고 가정하고 작성한 코드인데, 항상 어떤 예외 상황이 발생할 수 있을지 고민하고, 그에 대한 예외 처리를 적절히 해주는 것은 매우 중요하다. (즉, n이 음수라면, Exception을 throw 혹은 raise 하는 코드를 넣어주는 것이다.)

이제 베이스케이스에 대한 종료조건을 넣어줘서 정상 종료하겠지만 함수호출 횟수를 (아주 미미하지만)줄이고 싶다면 다음과 같이 조건을 추가해줄 수도 있다.

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

피보나치로 베이스케이스에 대한 감을 잡아보자.

피보나치 수열은 다음과 같다. 혹시 처음 보신 분이 있다면 규칙을 찾아서 13 다음의 숫자를 맞춰보자. 1,1,2,3,5,8,13,.... 답은? 21이다. 피보나치의 경우, 인접 3항간 점화식이 필요한 수열이다. 어려울 것 없다. 이것에 대한 설명은 다음 점화식을 보도록 하자.

F_n = F_n-1 + F_n-2

우리가 n번째 수열을 나타내기 위해서는 n-1, n-2 이렇게 두개가 필요하다. 그래서 3항간 점화식이라고 하는 것이다.

그럼 우리가 앞에서 배운 Recursion 문제를 풀기 위한 스텝을 밟아보자. 우선, 여기서 문제가 무엇인가? 한개의 int 인자 n을 받아 피보나치 수열에서 푸는 것이다. 그 다음, 재귀적 구조를 찾을 수 있는가? 점화식에서 찾을 수 있다(F_n = F_n-1 + F_n-2). 그럼 마지막으로 베이스 케이스는 무엇인가? 작은 숫자로 예를 들어보자. 3이라는 인자가 주어졌을 때, 다음과 같은 상황일 것이다.
F₃ = F₂ + F₁
아, 이제 2와 1을 인자로 받은 경우를 생각해보자.
F₂ = F₁ + F_{0 보통 1항부터 시작하지만 0항인 경우 0으로 설정할수도 있으니 틀린 것은 아니지만 여기선 1까지만 취급하기로 한다.}
F₁ = F₀ + F_-1 ====> ???
앞에서 무한루프의 악몽이 생각나지 않는가?
베이스 케이스를 찾는 방법은 크게 어렵지 않다. 다시 상기시키자면, 가장 기본이 되는 값, 즉 적어도 답이 이미 있어야 하는 케이스들, 종점인 케이스를 찾으면 된다. 위에서 봤듯이 2와 1을 넣었을 때, 우리가 해결해야하는 1항을 넘어선 0항과 -1항이 요구된다. 즉, 2와 1이 바로 베이스 케이스이다. 2개다. 사실, 굳이 피보나치 수열을 예시로 든 이유는 베이스케이스 개수에 대해 얘기하고 싶어서였다. 베이스케이스가 아까 팩토리얼에서는 1개였고, 피보나치 수열에서는 2개다. 어떤 차이가 있을까? 사실 뭔가 대단히 있는 것처럼 말을 꺼낸 것 같은데, 사실 내가 얘기할 내용은 매우 단순하다. 팩토리얼에서 재귀적 구조는 자기보다 1 작은 문제로 계속 쪼개어 나갔다. 하지만 피보나치에서는 자기보다 1 작고, 2 작은 문제로 쪼개어진다. 이게 끝이다. 2 작은 문제로 쪼개어지기 때문에 적어도 2개가 필요한 것이다.

마치며..

사실 recursion에 대해서 말을 하려면 너무나도 할 얘기가 많다. 나도 이제 막 공부하는 단계이기 때문에 많이 아는 것은 아니지만, 내가 당장 생각나는 예시만 따져도 정말 새발의 피만큼만 언급한 것 같다. 8-queen, hanoi, backtracking.... 하지만 아마 앞으로 글 쓰면서 계속해서 재귀를 사용한 구현이 있을 것이라 다음에 기회가 되면 좀 더 추가하거나 해야겠다.