재귀함수(Recursive function)은 함수 내부에서 자신을 다시 호출하는 함수를 말한다.

예를 들면 다음과 같다.

const factorial = n => {
    return n > 0 ? factorial(n - 1) : 1;
}

위의 factorial 함수는 팩토리얼을 계산하는 함수다.

n이라는 인자를 받아서 n이 양수이면 다시 자기 자신을 호출하며 n-1을 인자로 넘겨준다.

매 재귀호출마다 인자가 1씩 줄어들면서 n이 0이 되는 순간 재귀호출이 끝난다.

이처럼 재귀함수에서는 다음 호출시 넘겨주는 인자가 종료 조건으로 수렴해야한다. 그렇지 않으면 무한히 재귀호출을 하다가 콜스택이 오버플로우 되는 순간 프로그램이 멈춘다.

재귀함수는 반복문으로 치환할 수 있다.

위의 코드를 반복문으로 바꾸면 다음과 같다.

const factorial = (n) => {
    let result = 1;
    for (let i = n; i > 1; i--) {
        result = i * result;
    }
    return result;
};

일반적으로 함수가 실행될 때 마다 callstack을 잡아먹는 재귀함수는 반복문보다 퍼포먼스가 떨어진다.

하지만 반복문으로 구현했을 때 심하게 복잡해지거나 재귀함수를 사용해서 간단하고 깔끔하게 해결할 수 있다면 재귀함수를 쓰는 것이 좋다.

재귀함수의 특징을 정리해보면,

• 호출시마다 콜스택을 잡아먹음 (콜스택의 크기에 따라 호출 횟수 제한이 있음)
• 무한루프가 되지 않도록 탈출조건으로 수렴해야 함
• 반복문보다 퍼포먼스가 떨어짐 (콜스택을 사용하는 비용)
• 코드가 반복문에 비해서 단순해짐
• 수학적인 논리를 코드로 직관적으로 옮길 수 있음 (코드가 논리적으로 맞다는 것을 증명하기 쉬움)