함수16 - 재귀 함수

"함수"

 

7.2. 재귀 함수

함수가 자기 자신을 호출하는 것을 재귀 호출(recursive call)이라 한다. 재귀 함수(recursive function)는 자기 자신을 호출하는 행위, 즉 재귀 호출을 수행하는 함수를 말한다.

 

재귀 호출을 통해 반복 연산을 간단하게 구현할 수 있다. 예를 들어 팩토리얼은 재귀 호출로 간단히 구현할 수 있다.

// 팩터리얼(계승)은 1부터 자신까지의 모든 양의 정수의 곱이다.
// n! = 1* 2 * ... * (n-1) * n
function factorial(n) {
	// 탈출 조건: n이 1 이하일 때 재귀 호출을 멈춘다.
	if (n <= 1) return 1;
	// 재귀 호출
	return n * factorial(n - 1);
}

console.log(factorial(0));	// 0! = 1
console.log(factorial(1));	// 1! = 1
console.log(factorial(2));	// 2! = 2 * 1 = 2
console.log(factorial(3));	// 3! = 3 * 2 * 1 = 6
console.log(factorial(4));	// 4! = 4 * 3 * 2 * 1 = 24
console.log(factorial(5));	// 5! = 5 * 4 * 3 * 2 * 1 = 120

재귀 함수

재귀 함수는 자신을 무한 재귀 호출한다. 따라서 재귀 함수 내에는 재귀 호출을 멈출 수 있는 탈출 조건을 반드시 만들어야 한다. 위 예제의 경우 인수가 1 이하일 때 재귀 호출을 멈춘다. 탈출조건이 없는 경우 함수가 무한 호출되어 stack overflow 에러가 발생한다.

 

factorial 함수 내부에서 자기 자신을 호출할 때 사용한 식별자 factorial은 함수 이름이다. 함수 이름은 함수 몸체 내부에서만 유효하가. 따라서 함수 내부에서는 함수 이름을 사용하여 자기 자신을 호출할 수 있다. 함수 표현식으로 정의 한 함수 내부에서는 함수 이름은 물론 함수를 가리키는 식별자로도 자기 자신을 재귀 호출할 수 있다. 단, 함수 호출은 반드시 함수를 가리키는 식별자로 해야 한다.

// 함수 표현식
var factorial = function foo(n) {
	// 탈출 조건: n이 1 이하일 때 재귀 호출을 멈춘다.
    if (n <= 1) return 1;
    // 함수를 가리키는 식별자로 자기 자신을 재귀 호출
    return n * factorial(n - 1);
    // 함수 이름으로 자기 자신을 재귀 호출할 수도 있다.
    // return n * foo(n - 1);
};

console.log(factorial(5));	// 5! = 5 * 4 * 3 * 2 * 1 = 120

 

대부분의 재귀 함수는 for 문이나 while 문으로 구현이 가능하다. 위 팩토리얼 예제를 반복문으로 구현하면 아래와 같다.

function factorial(n) {
	if(n <= 1) return 1;
    
	var res = n;
	while (--n) res *= n;
	return res;
}

console.log(factorial(0));	// 0! = 1
console.log(factorial(1));	// 1! = 1
console.log(factorial(2));	// 2! = 2 * 1 = 2
console.log(factorial(3));	// 3! = 3 * 2 * 1 = 6
console.log(factorial(4));	// 4! = 4 * 3 * 2 * 1 = 24
console.log(factorial(5));	// 5! = 5 * 4 * 3 * 2 * 1 = 120

재귀 함수는 반복 연산을 간단히 구현할 수 있다는 장점이 있지만 무한 반복에 빠질 수 있고, 이로 인해 stack overflow 에러를 발생시킬 수 있으므로 주의해서 사용해야 한다. 따라서 재귀 함수는 반복문을 사용하는 것 보다 재귀 함수를 사용하는 것이 보다 직관적으로 이해하기 쉬을 때에만 한정적으로 사용하는 것이 바람직하다.