재귀함수란?

코딩테스트 문제를 풀다보면 한 번쯤 유용하게 쓸 일이 생긴다.

 

재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수이다.

코드를 살펴보자

 

function printNum(number) {
if(number === 0) return //탈출조건

printNum(number - 1);
console.log(number)
}

printNum은 전달받은 인수 number를 출력하는 함수이다.

 

함수에 있는 if문은 탈출 조건으로 재귀함수에서 필수 요소이다.

만약 탈출조건이 없거나 만족되지 않는다면 계속 본인자신을 호출해서 stack over가 될 것이다.

 

함수를 이제 실행해보자.

printNum(3)을 실행하면

printNum(3) {
if(number === 0) return
} // 1

printNum(2) {
if(number === 0) return
} // 2

printNum(1) {
if(number === 0) return
} // 3

printNum(0) {
if(number === 0) return
} // 4

이런 순서로 메모리에 쌓이게 된다.

제일 마지막에 실행되는 함수는 printNum(0)이고 탈출 조건을 만족했기 때문에 return되어 printNum(0)을 호출한

printNum(1)로 되돌아간다. 

 

그럼 출력은 언제 될까?

printNum(0) {
if(number === 0) return
} // 1

printNum(1) {
console.log(1)
} // 2

printNum(2) {
console.log(2)
} // 3

printNum(3) {
console.log(3)
} // 4

이런 순서로 다시 되돌아가며 숫자가 출력된다. 그러면 우리는 1,2,3을 순서대로 얻을 수 있다.

 

재귀함수를 다룰 때 재귀함수를 호출하는 시점을 기준으로

위에 있는 코드와 아래 있는 코드는 실행 시점이 완전히 달라진다.

이 점이 재귀함수가 갖는 큰 특징이고 유의해야 할 점이다.

 

재귀함수를 응용한 BFS,DFS 등 다양한 알고리즘이 있으니 개념을 알아두면 좋을 것 같다.