"맛보기에 이어서"
오늘은 재귀 (Recursion) 를 다뤄보려고 합니다. 참고로 제목이나 본문에 가급적 한 번 이상 영어를 병기하는 이유는 이런 작업들이 나중에 영어로 검색하는 데 도움이 되지 않을까 싶은 마음 때문입니다. 아무래도 프로그래밍 관련해서는 영어로 된 자료가 비교할 수 없을 만큼 많으니까요.
프로그래밍은 어떤 문제를 해결하는 과정이라고 할 수 있습니다. 이 때 재귀라는 것은 주어진 문제를 잘게 쪼개어 해결하는 것인데요. 구조적으로 더 작은 문제를 해결할 수 있는 코드를 구현하고, 이를 더 큰 문제에 반복적으로 대입하는 것이 재귀라고 할 수 있습니다. 이 때 재귀 함수는 실행되는 과정에서 자기 자신을 다시 호출한다는 특징을 가지게 되죠.
계승 또는 팩토리얼 (factorial) 은 재귀 함수에서 자주 등장하는 예시입니다. 흔히 숫자 뒤에 ! 를 붙여서 표현하는데요. 1부터 자기 자신까지의 자연수를 모두 곱하는 것을 말하며, n! 이라고 표현합니다. 즉 3! 은 3*2*1 === 6 이 되는 것이고 5! 은 5*4*3*2*1 === 120 이 되는 것입니다.
이를 코드로 표현하면 이렇습니다.
function factorialIteration(n) {
let result = n;
for (let i = n - 1; i > 1; i--) {
result = result * i;
}
return result;
}
// 반복문 (iteration) 을 활용한 팩토리얼
function factorialRecursive(n) {
if (n <= 1) return 1;
return n * factorialRecursive(n - 1);
}
// 재귀 (Recursion) 를 활용한 팩토리얼위의 예시를 보면 반복문에서는 볼 수 없었던 패턴이 등장합니다. 바로 함수 내부에서 자기 자신을 다시 호출하는 경우입니다. 재귀를 이용한 팩토리얼의 함수 내부를 보시면 리턴문에서 다시 factorialRecursive 를 호출하고 있는데요. 이것을 재귀 호출이라고 합니다.
재귀호출이 이루어지면 함수는 다음처럼 작동합니다. n 으로 3 이라는 숫자가 주어진 경우를 살펴보겠습니다.
factorialRecursive(3) {
// if (3 <= 1) return 1; // 조건에 맞지 않아 다음으로 넘어감
return 3 * fatorialRecursive (3 - 1) { // 2가 들어간 함수
// if (2 <= 1) return 1; // 조건에 맞지 않아 다음으로 넘어감
return 2 * factorialRecursive(2 - 1) { // 1이 들어간 함수
if (1 <= 1) return 1; // 조건에 해당
// return 1 * factorialRecursive(1 - 1)
}이렇게 재귀 호출이 최종적으로 다시 자기 자신을 호출하지 않는 경우를 base case 라고 합니다. (반대로 반복적으로 진행되는 부분은 recursive case 라고 합니다.) 재귀함수는 무한반복할 수 있기 때문에 base case 를 이용해 탈출 조건을 명시해줘야 무한반복을 멈추고 결과를 리턴합니다. 위의 식에서는 함수 내부의 첫 번째 문장인 if (n <= 1) return 1; 을 base case 라고 볼 수 있습니다.
사실 모든 재귀 함수는 반복문을 활용해서 구현이 가능하다고 합니다. 그럼에도 재귀를 사용하는 것은 재귀를 사용했을 때 코드가 간결해질 뿐 아니라, 이해하는 데도 쉽기 때문이라고 하는데요. 재귀는 알고리즘을 푸는데 있어서도 빼놓을 수 없는 개념이라고 하는 만큼 반드시 확실하게 알고 넘어가야 한다고 합니다.
재귀에 있어서 중요한 것은 어떻게 문제를 쪼개고, 그 안에서 반복적으로, 다시 말해 재귀가 가능한 요소를 발견하느냐 인 것 같습니다. 위에서 사진으로 소개한 '하노이의 탑' 같은 경우도 재귀로 구현이 가능하다고 하는데요. 이런 것도 능숙하게 다룰 수 있는 개발자가 될 수 있도록 오늘도 열심히 열공을 이어나가야겠습니다.
