TIL) 자바스크립트, 재귀함수 (Recursion)

재귀再歸 (Recursion)

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

재귀 (Recursive) vs 반복 (Iterative)

• 보통 재귀는 for문과 같은 반복문과 비교가 많이 된다. 경우에 따라 재귀를 이용한 코드가 더 이해하기 쉬울 수 있다. 따라서 프로그래머라면 두 가지 방법 모두 명확하게 알고 있어야 한다.

스택 (Stack)

• 재귀 호출을 이해하기 위해서는 스택(Stack)이라는 자료 구조를 먼저 살펴보는 것이 좋다. 왜냐하면 컴퓨터는 호출 스택이라고 불리는 스택 사용하여 함수를 실행하기 때문이다.

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

• 스택은 자료의 입출력이 언제가 목록의 한 쪽 끝에서만 일어난다. 즉, 자료를 한 쪽 끝에서만 넣거나 뺄 수 있는 선형 구조이며 가장 나중에 들어간 자료가 가장 먼저 나온다. 이것을 LIFO(Last In First Out)라고 부르기도 한다.

팩토리얼 (Factorial) 구하기

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을 저장하여 3 * factorial(3 - 1);이 되고 factorial(3 - 1)은 factorial(2)로 변환되어 실행한다.
3. n의 값으로 2가 전달된다. stack에 2를 저장하고 3 * factorial(2 - 1)은 factorial(1)로 변환되어 실행한다.
4. n의 값으로 1이 전달된다. n이 1이면 1을 리턴하고 함수를 종료한다.
5. factorial(1)이 1을 return하고 종료하였으므로 2 * 1을 연산하고 그 값인 2를 return을 한다.
6. return이 된 2와 3을 곱한 후 그 값인 6을 리턴하고 모든 함수가 종료된다.

3 * factorial(3 - 1);           3 * 2 = 6 
         ↓							↑
2 * factorial(2 - 1);           2 * 1 = 2
		 ↓							↑
	 1 return					1 return

Base case (Termination case)

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

}

• 위의 코드처럼 작성을 하게 되면 심각한 오류를 가져온다.

Maximum call stack size exceeded

• 위의 코드를 실제로 실행하게 되면 Maximum call stack size exceeded. 최대 호출 스택 사이즈가 초과되었다. 이 부분이 바로 우리가 재귀 함수를 사용할 때 가장 유의해야하는 부분이다.

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

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

정리

1. 문제를 동일한 방식으로 계속 쪼개기 → 쪼개는 방식이 recursive case

2. 더 이상 안 쪼개지면 그것이 base case → 재귀 함수의 탈출 조건

3. base case 해결하기 → 쪼개졌던 문제가 한 번에 해결