이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
재귀는 함수형 프로그래밍을 위한 강력한 도구이며 루프를 사용하는 것보다 더 우아하게 많은 문제를 해결하는 데 사용할 수 있습니다. 이 게시물에서는 재귀가 무엇인지, 어떻게 작동하는지, JavaScript에서 효과적으로 사용하는 방법에 대해 살펴보겠습니다.
재귀는 문제를 더 작은 하위 문제로 나누어 해결하는 기술입니다. 이를 위해 작업 중인 하위 문제를 직접 해결할 수 있는 지점에 도달할 때까지 자신을 재귀적으로 호출하는 함수를 정의합니다.
예를 들어, 숫자 n
의 계승을 계산하고 싶다고 합시다. 우리는 n
을 인자로 받고 n * (n-1) * (n-2) * ... * 1
을 반환하는 factorial
함수를 정의함으로써 이것을 재귀적으로 할 수 있습니다. factorial(5)
를 호출하면 함수는 5 * 4 * 3 * 2 * 1
(120)을 반환합니다.
재귀가 어떻게 작동하는지 이해하려면 함수가 호출될 때 어떤 일이 발생하는지 이해해야 합니다. 함수가 호출되면 JavaScript는 함수에 대한 새 실행 컨텍스트를 만듭니다. 이 실행 컨텍스트에는 함수의 인수, 지역 변수 및 함수가 호출된 지점에 대한 정보가 포함됩니다.
함수가 자신을 호출할 때마다 매번 새로운 실행 컨텍스트를 생성합니다. 가장 최근 컨텍스트가 맨 위에 있는 실행 컨텍스트 스택으로 생각할 수 있습니다. 함수가 자신을 호출할 때마다 새 실행 컨텍스트가 스택 맨 위에 추가됩니다.
함수가 더 이상 자신을 호출하지 않는 지점에 도달하면 실행 컨텍스트가 스택에서 하나씩 팝되고 함수는 계산한 값을 반환합니다.
재귀가 작동하려면 기본 사례와 재귀 사례를 정의해야 합니다. 기본 사례는 함수가 자신을 호출하지 않고 직접 문제를 해결할 수 있는 지점입니다. 재귀 사례는 함수가 자신을 호출하는 경우입니다.
우리의 계승 예에서 기본 사례는 n
이 1일 때입니다. 왜냐하면 그것이 우리가 곱셈을 중지하고 1을 반환할 수 있는 지점이기 때문입니다. 재귀 사례는 n
이 1보다 클 때입니다. n-1
로 함수를 다시 호출해야 합니다.
함수가 자신을 호출하면 현재 실행 컨텍스트가 스택에 추가됩니다. 함수가 너무 많이 호출되면 스택 오버플로가 발생할 수 있습니다.
다행스럽게도 JavaScript에는 이 문제를 방지하는 데 도움이 되는 꼬리 호출 최적화라는 최적화 기능이 있습니다. 꼬리 호출 최적화는 함수의 반환 값이 다른 함수 호출의 결과인 경우입니다. 이 경우 현재 실행 컨텍스트를 재사용할 수 있으므로 스택이 커지지 않습니다.
예를 들어 다음 함수는 꼬리 재귀 함수입니다.
function factorial(n) {
if (n === 1) {
return 1;
} else {
return n * factorial(n-1);
}
}
그러나 다음 함수는 반환 값이 다른 함수 호출의 결과가 아니기 때문에 꼬리 재귀가 아닙니다.
function factorial(n) {
if (n === 1) {
return 1;
} else {
return n * factorial(n-1) + 1;
}
}
재귀는 많은 문제를 해결하는 데 사용할 수 있지만 항상 최상의 솔루션은 아닙니다. 일반적으로 재귀는 다음과 같은 경우에 가장 잘 사용됩니다.
재귀는 연결된 목록 및 트리와 같은 데이터 구조를 만드는 데에도 사용할 수 있습니다.
재귀가 항상 문제에 대한 최선의 해결책은 아닙니다. 일반적으로 다음과 같은 경우 재귀를 피해야 합니다.
재귀의 몇 가지 예를 살펴보겠습니다.
앞에서 보았듯이 재귀를 사용하여 숫자의 계승을 계산할 수 있습니다. 이것은 더 작은 하위 문제로 나눌 수 있는 문제의 좋은 예이며 하위 문제가 충분히 작을 때 직접 해결할 수 있습니다.
function factorial(n) {
if (n === 1) {
return 1;
} else {
return n * factorial(n-1);
}
}
재귀의 또 다른 일반적인 예는 n번째 피보나치 수를 계산하는 것입니다. 피보나치 수열은 각 숫자가 이전 두 숫자의 합인 일련의 숫자입니다. 따라서 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
n번째 피보나치 수를 계산하기 위해 n
을 인수로 사용하고 n-1
번째 피보나치 수와 n-2
번째 피보나치 수를 반환하는 재귀 함수를 사용할 수 있습니다.
function fibonacci(n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
재귀의 또 다른 예는 두 숫자의 최대 공약수(GCD)를 찾는 것입니다. 두 숫자의 GCD는 두 숫자를 균등하게 나누는 가장 큰 숫자입니다.
유클리드 알고리즘을 사용하여 두 숫자의 GCD를 찾을 수 있습니다. 알고리즘은 다음과 같습니다.
b
가 0이면 GCD는 a
입니다.b
의 GCD와 a / b
의 나머지 부분입니다.다음과 같이 JavaScript에서 이 알고리즘을 구현할 수 있습니다.
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a % b);
}
}
이번 포스트에서는 재귀가 무엇인지, 어떻게 작동하는지, JavaScript에서 효과적으로 사용하는 방법에 대해 알아보았습니다. 우리는 또한 재귀를 사용하여 해결할 수 있는 문제의 몇 가지 예를 보았습니다.
재귀는 함수형 프로그래밍을 위한 강력한 도구이지만 항상 문제에 대한 최상의 솔루션은 아닙니다. 일반적으로 문제를 더 작은 하위 문제로 나눌 수 있고, 하위 문제가 충분히 작을 때 문제를 직접 해결할 수 있고, 문제의 구조가 재귀 솔루션에 적합한 경우 재귀를 사용해야 합니다.