13. 재귀함수

💫재귀함수란?

 

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

 

💫스택(Stack)

 

재귀 호출을 이해하는 것에 앞서 스택(Stack)이라는 자료 구조를 이해해야 한다.

 

Stack : 자료의 입출력이 한 방향에서만 이루어지는 자료구조. 

 

 

프링글스를 중간부터 먹을 수는 없다. 맨 아래 있는 프링글스를 먹으려면 맨 위에서부터 차근차근 먹어야한다. 즉, 

한 쪽 끝에서만 넣거나 뺄 수 있는 선형 구조이며 가장 나중에 들어간 자료가 가장 먼저 나온다. 이 것을 LIFO(Last In First Out) 으로 부르기도 한다.

 

💫팩토리얼 (Factorial) 구하기 

 

코드로 넘어가기 전, 숫자 그대로 팩토리얼을 나열해보면 

 

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);
}

factorial(4);

 

 

문제는 위와 같이 쓰면 다음과 같은 에러가 발생한다.

 

 

종료 시점이 없기 때문에 코드를 계속 실행하여 발생하는 에러이다.

이렇게 재귀 호출을 중단시키는 조건 문장을 Base Case 또는 Termination Case 라고 한다. 

 

위의 코드의 경우, factorial(4), factorial(3), factorial(2), factorial(1), factorial(0), factorial(-1), factorial(-2) ...

이렇게 음수의 영역까지 호출하며 순차적으로 스택을 쌓아 어느 순간 정해진 메모리 용량을 초과하여 위와 같은 에러를 발생시키는 것이다. 

 

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

factorial(4);

 

 

Base Case를 추가해주니 정상적으로 출력되는 것을 볼 수 있다.

작동 방식은 다음과 같다.

 

 

 

💫재귀 함수의 단점 

 

재귀 함수를 사용하면 함수의 호출이 스택에 쌓이게 되고, 위에서부터 차례대로 값을 반환하기 전에는 계속 메모리 공간을 차지하게 된다. 이러한 이유 때문에 호출 스택이 커져서 메모리를 크게 소비할 수 있다. 따라서 상황에 따라 반복문과 재귀 함수를 적절하게 사용할 줄 알아야한다.

 

---

 

💫referrence 

 

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

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