재귀함수(Recursive Function)는 여러가지 문제해결 방법론 중의 하나로, 함수가 자기 자신을 반복적으로 호출하여 문제를 해결합니다.
이는 기본적으로 종료 조건과 재귀 조건을 가지고 있어야 합니다.
Table of Contents
재귀함수 기본 구조
function recursiveFunction() {
if (/* Base Case */) {
return /* 종료 값 */;
} else {
/* Recursive Case */
return recursiveFunction(/* 매개변수 */);
}
}Base Case: 재귀 호출을 종료할 조건을 말합니다. 이 조건을 만나면 더 이상 재귀 호출을 하지 않고 결과 값을 리턴합니다.
Recursive Case: 자기 자신을 호출하는 부분으로 문제를 더 작은 단위로 분할하여 해결합니다.
예제 1: 팩토리얼 계산
팩토리얼은 주어진 수 n에 대해 n! = n * (n-1) * (n-2) * … * 1 을 계산하는 함수입니다.
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
console.log(factorial(5));
위의 예제 코드를 개발자 도구를 사용하여 테스트 해보면 이미지와 같은 결과를 얻을 수 있습니다.
팩토리얼 계산의 종료 조건은 n === 0 인 경우입니다. 이 때 1을 리턴합니다.
재귀 조건은 n * factorial(n - 1) 로 자기 자신을 호출하면서 n을 줄이며 계산을 합니다.
계산 결과를 console.log() 메소드를 활용해 콘솔에 출력하면 120임을 알 수 있습니다.
예제 2: 피보나치 수열
피보나치 수열은 각 항이 이전 두 항의 합으로 구성된 수열을 말합니다.
예를 들어, F(0) = 0, F(1) = 1 일 때 F(n) = F(n-1) + F(n-2) 로 정리할 수 있습니다.
function fibonacci(n) {
if (n === 0) {
return 0;
} else if (n === 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
console.log(fibonacci(6));
이번에는 종료 조건이 두 가지 입니다. n이 0일 때는 0을 n이 1일 때는 1을 리턴합니다.
재귀 조건에서는 fibonacci(n - 1) + fibonacci(n - 2) 로 자기 자신을 호출하여 두 수의 합을 구합니다.
예제 3: 배열의 합 구하기
주어진 배열의 모든 요소의 합을 구하는 문제는 여려가지 다양한 방법으로 풀 수 있지만 재귀적으로도 풀 수 있습니다.
function sumArray(arr) {
if (arr.length === 0) {
return 0;
} else {
return arr[0] + sumArray(arr.slice(1));
}
}
sumArray([1, 2, 3, 4, 5]);
종료 조건으로 배열의 길이가 0이면 0을 리턴합니다.
재귀 조건에서는 slice() 메소드를 사용하여 첫 번째 값과 배열의 나머지 값을 반복하여 더하게 합니다.
예제 4: 트리 순회 (중위 순회)
트리는 데이터를 계층적 구조로 관리하는 자료형으로 각 노드는 자식 노드를 가지고 있습니다.
다음은 이러한 트리 구조를 순회하는 예제로 괄호를 가지는 계산식 계산에서 계산 우선순위에 응용할 수 있습니다.
function inorderTraversal(node) {
if (node !== null) {
inorderTraversal(node.left); // 왼쪽 자식 노드 순회
console.log(node.value); // 현재 노드 출력
inorderTraversal(node.right); // 오른쪽 자식 노드 순회
}
}
const tree = {
value: 1,
left: {
value: 2,
left: { value: 4, left: null, right: null },
right: { value: 5, left: null, right: null }
},
right: {
value: 3,
left: null,
right: null
}
};
inorderTraversal(tree); // 4, 2, 5, 1, 3여기서 종료 조건은 더 이상 자식 노드가 없는 경우입니다.
재귀 조건은 왼쪽 자식 노드 먼저 순회하고 자기 자신, 오른쪽 자식 노드 순서로 순회합니다.
재귀함수 주의점
스택 오버플로우:
재귀 횟수가 너무 많아지면 스택 오버플로우 오류가 발생할 수 있습니다. 함수의 콜 명령은 스택에 저장되기 때문입니다.
이를 방지하기 위해 종료 조건을 명확히하고 이를 빨리 만족시킬 수 있도록 해야합니다.
성능:
함수를 재귀하는 방법은 일반 반복문 보다 느립니다. 예를 들어, 피보나치 수열 계산의 경우 재귀 방식으로 계산하면 중복 계산이 많이 일어납니다.
이런 경우 한번 계산한 항목을 캐시든 어떠한 형태로든 기억하게하는 Memoization 기법을 사용할 수도 있습니다.
재귀함수 정리
재귀 함수는 문제를 작은 단위로 나누어 해결하는 강력한 방법입니다.
주로 반복적인 구조나 계층적인 자료 구조를 처리할 때 유용합니다.
하지만 종료 조건을 명확히 설정하지 않으면 무한 루프에 빠질 수 있으므로 종료 조건을 정확하게 정의해야 합니다.