[Algorithm] 재귀(Recursion)에 대해 쉽게 알아보자

💡 재귀

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재 참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출의 형태로 많이 사용된다.

▲ 재귀의 예

위의 이미지와 재귀는 무슨 상관관계가 있을까? 처음에는 하나의 큰 화면으로 시작해서 다른 화면을 담지 못할 때까지 점점 화면이 작아지는 것이 반복된다. 이처럼 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 문제를 해결함으로써 그 문제를 해결하는 것 즉, 문제가 간단해져서 바로 풀 수 있는 문제로 작아질 때(base case)까지 해결해보는 방식이 바로 재귀이다.

 

💡 재귀함수

함수 안에서 다시 자신의 함수를 호출(재귀 호출)하면서 로직을 처리하는 경우를 말한다. 

** ☝🏻 여기서 잠깐, 재귀 호출을 이해하기 위해서는 스택을 먼저 이해하는 것이 좋습니다.

우리의 컴퓨터는 호출 스택이라고 불리는 스택을 사용하여 함수를 실행하는데, 호출 스택은 일반적인 프로그래밍에서도 중요하지만 재귀를 사용할 때 더욱 중요하다. 예를 들어, 우리가 매일 아침 할 일을 하나씩 적어서 포스트잇으로 붙여놓는다고 가정해볼 것이다. 다만, 포스트잇은 오로지 한 곳에만 겹쳐서 붙여 놓을 수 있다. 가장 위에 적힌 할 일을 해결하면 위에서부터 포스트잇을 뗄 수 있고 다음 일을 수행하면 또 포스트잇을 떼는 작업을 하게 된다. 이렇게 할 일의 항목을 적어 포스트잇을 붙이는 것(자료를 넣는 것)을 PUSH라고 하며 붙인 포스트잇을 떼어내고 포스트잇에 적힌 내용을 읽는 것(자료를 빼내는 것)을 POP이라고 한다. 바로 이러한 자료구조를 바로 '스택'이라고 한다. 스택은 자료의 입출력이 언제나 목록의 한쪽 끝에서만 일어난다. 즉, 자료를 한 쪽 끝에서만 넣거나 뺄 수 있는 선형 구조이며 가장 나중에 들어간 자료가 가장 먼저 나온다. 이것을 LIFO(Last In First Out)라고 부르기도 한다.

 

💡 재귀함수의 예 - 팩토리얼(Factorial) 구하기

재귀 함수를 설명할 때 가장 많이 등장하는 예제는 바로 팩토리얼 구하기이다. 팩토리얼이란 자기 자신부터 시작해서 1씩 감소한 숫자들을 곱한 값이다.

먼저, 팩토리얼을 반복문을 사용한 코드로 작성해보면 다음과 같다.

function factorial (n) {
var result = 1;
for (var i = n; i >= 1; i--) {
result *= i;
}
return result;
}

 

n부터 1까지의 수를 반복하여 result변수에 곱한다. 곱셈을 해야 하므로 result 변수의 초기값은 당연히 1이어야 한다.

다음으로 재귀 함수로 작성해보면 다음과 같다.

factorial(5) = 5 * 4 * 3 * 2 * 1 = 5 * factorial(4);

factorial(4) = 4 * 3 * 2 * 1 = 4 * factorial(3);

factorial(3) = 3 * 2 * 1 = 3 * factorial(2);

factorial(2) = 2 * 1 = 2 * factorial(1);

factorial(1) = 1;

여기서부터 어떤 규칙이 보이기 시작한다. 저 규칙대로라면 factorial(n) = n * factorial(n - 1);이 될 것이다.

이 것을 코드로 표현해보면 다음과 같다.

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

 

하지만 위의 코드는 심각한 오류를 가지고 있다. 실제로 실행해보면 최대 호출 스택 사이즈가 초과되었다라는 에러가 발생한다. 바로 이 부분이 재귀 함수를 사용할 때 가장 유의해야 하는 부분이다. 

재귀 함수를 작성하여 호출하면 함수는 자기 자신을 계속해서 호출하여 실행한다. 이때, 특정 조건이 되었을때 재귀 호출을 종료하는 문장이 반드시 하나 이상 존재해야 하는데, 이렇게 재귀 호출을 중단시키는 조건을 Base case 또는 Termination case라고 한다.

위의 팩토리얼 코드는 Base case가 없으므로 factorial(4), factorial(3), .... , factorial(-1), factorial(-2),..... 음수의 영역까지 계속 호출하며 순차적으로 스택에 쌓여질 것이고 어느 순간 정해진 메모리 용량을 초과하여 에러 메세지를 출력한다.

그러므로 우리는 다음과 같이 재귀 호출을 종료하는 Base case로 n이 1이 되었을 때, 1을 return하는 문장을 반드시 추가해줘야한다.

function factorial (n) {
if (n === 1) { // Base case, Termination case
return 1;
}
return n * factorial(n - 1);
}
factorial(3); // 6

 

위 코드의 실행 순서는 다음과 같다.

 

1. 먼저 파라미터 n의 값으로 3이 전달된다.
2. stack에 3을 저장하고 factorial(3 - 1) = factorial(2)을 실행한다.
3. n의 값으로 2가 전달된다. stack에 2를 저장하고 factorial(2 - 1) = factorial(1)을 실행한다.
4. n의 값으로 1이 전달된다. n이 1이면 1을 리턴하고 함수를 종료한다.
5. factorial(1)이 1을 return하고 종료하였으므로 2 * 1을 연산하고 그 값인 2를 return한다.
6. 리턴된 2와 3을 곱한 후 그 값인 6을 리턴하고 모든 함수가 종료된다.

 

💡 재귀함수의 장단점

알고리즘을 재귀로 표현했을 때 가독성이 좋아지지만, 함수의 호출이 스택에 차곡 차곡 쌓이게 되고, 위에서부터 차례대로 값을 반환하기 전까지 계속 메모리 공간을 차지하고 있기 때문에 메모리의 엄청난 소비가 따르게 된다. 이러한 이유때문에 재귀를 사용하는 것보다 반복문을 사용했을 때 더 성능이 좋은 경우가 많다. 그러므로 상황에 따라 적절한 방법을 골라서 사용할 수 있어야 한다.

 

 

 

[참고자료]

https://im-developer.tistory.com/102

[JS/Recursion] 자바스크립트, 재귀함수에 대하여 (Recursion)