재귀함수

재귀함수란?

함수가 자기 자신을 호출하는 행위를 가리켜 재귀 호출(recursive call) 이라고 합니다. 이러한 재귀 호출을 수행하는 함수를 재귀 함수 라고 합니다.

 

재귀함수 예시로 유명한 팩토리얼 예제를 간단히 코드로 옮겨보겠습니다.

function fact(n){
  if(n <= 1) return 1;
  return n * fact(n-1);
}
fact(5);  // 120

이 예제는 5에 대한 팩토리얼을 구하는 예제입니다. fact함수 안에는 매개변수 n이 1보다 작거나 같으면 1을 return 하면서 이 재귀함수를 종료하는 조건을 넣어주었습니다. 종료조건이 충족하기 전까지는 매개변수 n 에 fact함수를 재귀호출하여 곱을 return 하고 있는데요, fact함수를 재귀호출 할 때는 전달인자로 n-1 을 전달해주고 있습니다. 

따라서, 이 재귀함수의 출력 값은 5 *  4 * 3 * 2 * 1 이 되어 120이 될 것 입니다.

 

재귀의 중요한 3가지 특성

모든 재귀함수는 3가지의 특성을 갖습니다.

 

1. 종료조건

위의 예시에서 if의 조건문 처럼 if( 이 조건에 맞는 값이 들어온다면 ) { 종료 }; 와 같이 종료 조건이 들어갑니다. 이 종료 조건은 재귀의 안전장치라고 볼 수 있습니다. 조건에 맞지 않는 값이 들어왔을 때, 재귀가 계속하여 동작하는 것을 방지해줍니다. 

위의 예제에서 if( n <= 1) { return 1; } 은 fact함수의 종료 조건 입니다. 그래서 우리는 0 이하의 값이 들어 왔을 때, 이 함수가 작동하지 않길 원합니다.

만약, 이 종료조건이 없이 계속해서 재귀 호출을 하게 된다면 계속해서 자기 자신을 호출하므로 무한루프에 빠져 결국엔 아래와 같은 콜스택 오버 에러가 뜰 것 입니다. 

Uncaught RangeError: Maximum call stack size exceeded

 

2. 기반조건

1번의 예시에 있는 조건문이 종료 조건을 위한 것이였다면 이 기반 조건은 간단하게 if( 이 조건에 맞는 값이 들어온다면) { 실행 }; 과 같이 볼 수 있습니다. 이 조건 역시 재귀 함수를 멈춘다는 점을 감안하면, 기반 조건 또한 어쩌면 재귀의 종료조건과 비슷합니다.

종료조건은 조건에 맞지 않는 값을 잡아내는 조건문이라면 이 기반조건은 현재 실행하고 있는 재귀 함수의 목적입니다. 

위의 예제에서의 기반조건은 if( n <= 1) { return 1; } 이 종료 조건이면서 기반 조건입니다. 왜냐하면 n 이 0 이하의 값이 된다면 팩토리얼을 구하는데 성공한 것이라고 볼 수 있기 때문입니다.

 

3. 재귀

재귀란 함수가 자기 자신을 호출하는 것 이라고 배웠습니다. 위의 팩토리얼 예제에서 return n * fact( n - 1 ); 이 부분이 실제로 재귀가 일어나는 곳입니다. fact()함수는 매개변수로 들어온 값 n이 fact( n -1 ) 함수의 결과 값으로 곱해진 어떠한 값을 반환합니다.

즉, n값으로는 fact함수를 호출하면서 전달인자로 넣어준 5 이고, fact( n - 1)은 5 - 1, 4 - 1 ... 이렇게 계속해서 5 *  4 * 3 * 2 * 1 이 되어 재귀호출을 진행할 것입니다

 

재귀함수를 반복문으로 표현해보기

 

위의 예제에서 보면 재귀호출 또한 반복문처럼 조건문이 있고 조건에 충족할 때 까지 반복적으로 재귀호출을 해주기 때문에 아래 예제와 같이 반복문으로 표현할 수도 있습니다.

function fact(n) {
  let result = 1;
  for (let i = n; i > 0; i--) {
    result = result * i;
  }
  return result;
}
fact(5)  // 120

 

마지막으로 정리하면서 재귀함수의 장점과 단점을 살펴 보자면 다음과 같이 설명할 수 있겠습니다.

장점 : 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때 사용하면 좋고, 가독성을 높혀주기도 합니다.

단점 : 메모리를 많이 차지하며 성능이 반복문에 비해 느립니다. 함수를 호출 시 함수의 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장됩니다. 따라서, 재귀함수를 쓰게되면 함수를 반복적으로 호출하므로, 스택 메모리가 커지고, 호출하는 횟수가 많아지면 스택오버플로우가 발생할 수 있습니다.