[JS] 재귀 함수 (Recursive Function)

재귀 호출 : 함수가 자기 자신을 호출하는 것

 

재귀함수

자기 자신을 호출하는 (재귀 호출을 수행하는) 함수.

 

재귀함수를 표현하는 공식?이 있다.

 

1) 함수 표현식으로 함수를 선언

 

2) 재귀호출을 탈출할 조건

 

3)재귀 호출 및 리턴

 

왜 재귀함수를 사용할까?

재귀함수는 반복되는 처리를 위해 사용한다.

 

예를 들어 10부터 0까지 호출하는 함수가 있다고 가정해보자.

function countDown(n) {
for (let i = n; i >= 0; i--) console.log(i);
}
countDown (10);

위와 같이 for문을 사용해 이상없이 구현할 수 있지만 for문을 사용하지 않고 구현이 가능하다.

바로 재귀함수를 이용하면 된다.

function countDown(n) {
	if (n < 0) return; // 탈출조건: n이 0보다 작으면 리턴한다.
    console.log (n)
    function (n-1)
}
countDown (10);

비슷한 예제로 팩토리얼을 재귀함수로 표현해보자.

function factorial (n) {
	// 탈출 조건 n이 0이거나 1 즉 1이하일때 1을 리턴
    if (n <= 1); return 1;
    //재귀 호출
    return n * factorial (n-1); // n에서 시작해서 탈출조건을 만족할 때까지 -1씩 뺀 값을 곱해라.
}

 

일반적으로 재귀함수는 반복문 (for문, while문)으로 치환이 가능하다.

하지만 재귀함수에는 조심해야할 부분이 있는데 바로 탈출 조건을 달지 않으면 함수가 무한으로 호출돼 스택 오버플로우 (Stack Overflow)를 발생시킨다.

 

*스택 오버플로우 (Stack Overflow)란?

 

-프로그램이 호출 스택에서 이용 가능한 공간 이상을 사용하려고 시도할 때를 나타내며 프로그램 충돌을 일으킨다.

 

따라서 반드시 재귀함수만을 사용해야하거나 가독성이 극명하게 좋아지는 것이 아니라면 재귀함수보단 반복문을 추천한다고 한다.