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

재귀再歸 (Recursion)

프로그래밍에서 재귀(Recursion)란 자신을 정의할 때 자기 자신을 재참조하는 것을 말한다. 따라서 재귀 함수란 함수가 호출되어 실행할 때, 함수 내부에서 자기 자신을 다시 호출하는 재귀 호출(Recursive call)의 형태를 말한다.

 

 

 

Recursive vs Iterative

보통 Recursive와 Iterative가 많이 비교되곤 한다. Iterative는 '반복적인'이란 뜻을 가지고 있다. 즉, 우리가 흔히 사용하는 for문이나 forEach문과 같은 반복 연산을 가리킨다. 항상 그런 것은 아니지만 많은 경우에 Recursion으로 처리할 수 있는 문제는 Iterator로도 처리할 수 있고, 반대로 Iterator로 처리할 수 있는 것은 Recursion으로 처리할 수 있다. 어떤 방법으로 문제를 해결하느냐는 프로그래머의 마음이지만 때로는 Iterative 코드보다 Recursive 코드를 사용했을 때 더 이해하기 쉬운 코드가 될 때가 있다. 그러므로 우리는 두 가지 방법을 모두 명확하게 알고 있어야 한다.

 

 

 

스택 (Stack)

재귀 호출을 이해하기 위해서는 스택(Stack)이라는 자료 구조를 먼저 살펴보는 것이 좋다. 왜냐면 우리의 컴퓨터는 호출 스택이라고 불리는 스택을 사용하여 함수를 실행하기 때문이다. 호출 스택은 일반적인 프로그래밍에서도 중요하지만 재귀를 사용할 때 더욱 중요하다.

우리가 만약에 매일 아침에 그 날 할 일을 하나씩 적어서 포스트잇으로 붙여놓는다고 생각해보자. 다만 포스트잇을 여러 군데 붙여놓을 순 없고 오로지 한 곳에만 겹쳐서 붙여놓을 수 있다. 

 

1. 운동하기

2. 숙제하기

3. 시장 보기

 

이제 가장 위에 적힌 할 일을 해결하면 위에서부터 포스트잇을 뗄 수 있다. 맨 앞에 적힌 할 일은 "3. 시장 보기"이다. 시장 보기를 완료하고 나면 맨 위의 포스트잇을 제거하고 "2. 숙제하기"를 할 수 있다. 만약에 우리가 맨 위의 "3. 시장 보기"를 완료하지 못하면 다음 할 일을 할 수 없게 된다. 그러니까 우리는 맨 처음에 쓴 "1. 운동하기"를 하기 위해선 시장을 보고 포스트잇을 제거하고 숙제를 하고 포스트잇을 제거를 해야만 한다. 이 때, 할 일 항목을 적어 포스트잇을 붙이는 것을 push라고 하고 붙인 포스트잇을 떼어내고 포스트잇에 적힌 내용을 읽는 것을 pop이라고 한다.

 

 

자료를 넣는 것은 push, 빼는 것은 pop이라고 한다.

 

위에서 설명한 자료구조를 우리는 바로 스택(Stack)이라고 한다. 스택은 자료의 입출력이 언제나 목록의 한 쪽 끝에서만 일어난다. 그러니까 포스트잇을 붙이고 나면 우리는 그 위에만 포스트 잇을 붙일 수 있고 아래에 붙이는 것은 불가능한 것과 같다. 아래에 붙이려면 포스트잇을 떼어내어 제거한 후 다시 붙이는 방법밖에는 없다. 즉, 자료를 한 쪽 끝에서만 넣거나 뺼 수 있는 선형 구조이며 가장 나중에 들어간 자료가 가장 먼저 나온다. 이것을 LIFO(Last In First Out)라고 부르기도 한다.

 

 

 

팩토리얼 (Factorial) 구하기

재귀 함수를 설명할 때 가장 많이 등장하는 예제 코드가 바로 팩토리얼 구하기이다. 팩토리얼이란 자기 자신부터 시작해서 1 감소한 숫자들을 곱한 값이다. 예를 들어서 5!은 5 * 4 * 3 * 2 * 1 = 120이다.

 

 

팩토리얼을 먼저 Iterative 코드로 작성해보면 다음과 같다.

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

 

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

 

 

이제 재귀 함수로 만들어보자. 만약에 factorial(5)부터 factorial(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);
}

 

언뜻 보면 위 코드는 그럴듯해 보이지만 심각한 오류를 가지고 있다.

 

 

위 코드를 실제로 실행해보면 브라우저는 지구 끝까지 갈 기세로 코드를 계속해서 실행하다가 어느 시점에 저런 에러를 출력하고 멈출 것이다. Maximum call stack size exceeded. 최대 호출 스택 사이즈가 초과되었다. 이 부분이 바로 우리가 재귀 함수를 사용할 때 가장 유의해야하는 부분이다. 

 

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

 

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

 

 

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

 

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

 

이제 위 코드는 완벽한 재귀 함수의 형태를 하고 있으며, 위 코드의 실행 순서는 다음과 같다.

 

 

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을 리턴하고 모든 함수가 종료된다.

 

 

 

 

factorial 함수에 대한 각각의 호출이 자신만의 n값의 사본을 가지고 있다는 사실을 꼭 기억해야 한다. 서로 다른 함수 호출에 대한 n값에는 접근할 수 없다.

 

 

 

재귀 함수를 사용했을 때의 단점

위에서 살펴봤듯이 재귀 함수를 사용하면 함수의 호출이 스택에 차곡 차곡 쌓이게 되고, 위에서부터 차례대로 값을 반환하기 전에는 계속 메모리 공간을 차지하고 있다. 그렇기 때문에 호출 스택이 너무 커져서 메모리를 엄청나게 소비할 수도 있다. 이러한 이유 때문에 재귀를 사용하는 것보다 반복문을 사용했을 때 더 성능이 좋은 경우가 많다. 그러므로 상황에 따라 적절한 방법을 골라서 사용할 수 있어야 한다.

 

 

 

---

※ 참고도서:

Hello Coding 그림으로 개념을 이해하는 알고리즘 / 마디트야 바르가바 지음 / 한빛 미디어