재귀
업데이트: 2007년 11월
재귀는 함수가 그 함수 자체를 호출하는 중요한 프로그래밍 기법입니다. 재귀의 한 가지 예는 순차 곱셈 계산입니다. 0의 계승은 1로 정의됩니다. 0보다 큰 정수 n의 계승은 1부터 n 범위에 있는 모든 정수를 곱한 값입니다.
재귀 사용
순차 곱셈을 계산하는 함수를 일반 문장으로 표현하면 다음과 같습니다.
"숫자가 0보다 작으면 버립니다. 정수가 아니면 버립니다. 숫자가 0이면 순차 곱셈 값은 1입니다. 숫자가 0보다 크면 이 숫자에 그 다음으로 적은 숫자의 순차 곱셈 값을 곱합니다."
0보다 큰 수의 계승을 계산하려면 최소한 하나의 다른 수에 대한 계승 값을 구해야 합니다. 함수에서는 현재 숫자에 대해 실행하기 전에 그 다음으로 작은 숫자에 대해 자신을 호출해야 합니다. 이것이 재귀의 한 예입니다.
재귀와 반복(루핑)은 밀접한 관계가 있습니다. 함수에서는 재귀나 반복을 사용하여 동일한 결과를 반환할 수 있습니다. 일반 계산에서는 둘 중의 하나의 기술을 이용하며 가장 자연스럽거나 더 적합한 기법을 선택하면 됩니다.
재귀를 사용하면 유용하지만, 결과 값을 반환하지 않거나 종료 지점에 도달하지 않는 재귀 함수를 만들 우려가 있습니다. 그러한 경우 컴퓨터에서는 무한 루프가 실행됩니다. 다음 예제를 참조하십시오. 계승 계산 설명에 있는 첫 번째 규칙(음수 처리 방법 중 하나)을 무시하고 임의 음수에 대한 계승 계산을 시도해 봅니다. 그러나 예를 들어 -24의 계승을 계산하려는 경우에는 -25의 계승을 계산해야 하므로 이 예제는 실패합니다. 그리고 -25의 계승을 계산하려면 먼저 -26의 계승을 계산해야 합니다. 영원히 종료 지점에 이르지 못합니다.
재귀를 사용할 경우 발생할 수 있는 다른 문제는 재귀 함수로 인해 시스템 메모리, 스택 공간 등 사용 가능한 모든 리소스가 소모될 수 있다는 것입니다. 재귀 함수는 자신을 호출하거나 원래 함수를 호출하는 다른 함수를 호출할 때마다 리소스를 사용합니다. 재귀 함수가 종료되면 리소스를 다시 사용할 수 있게 되지만 너무 많은 단계의 재귀가 이루어지는 함수의 경우 사용 가능한 모든 리소스를 사용해 버릴 수 있습니다. 이런 경우에는 예외가 throw됩니다.
그러므로 재귀 함수를 만들 때에는 매우 신중하게 설계하는 것이 중요합니다. 과다 또는 무한 재귀가 의심되는 경우에는 자신을 호출하는 횟수를 계산하고 호출 횟수에 대한 제한을 설정하도록 함수를 설계하여 자신을 호출하는 횟수가 임계값보다 더 많아지면 함수가 자동으로 종료되도록 합니다. 가장 적합한 최대 반복 횟수는 재귀 함수에 따라 다릅니다.
아래의 예는 순차 곱셈 함수를 JScript 코드로 작성한 것입니다. 함수에서 정수만 받아들이도록 형식 주석을 사용합니다. 잘못된 숫자, 즉 0보다 작은 수가 전달되면 throw 문에서 오류를 발생시킵니다. 그렇지 않으면 재귀 함수를 사용하여 계승 계산을 수행합니다. 이 재귀 함수는 계승 인수와 현재 재귀 단계를 계산하는 카운터의 두 인수를 사용합니다. 카운터가 최대 재귀 단계에 이르지 않으면 원래 숫자에 대한 계승 값이 반환됩니다.
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
이 프로그램은 다음과 같이 출력됩니다.
120
7.156945704626378e+118