자바스크립트 기본 문법 – 함수 – 5 – 재귀 함수
소제목: 재귀 함수란?
재귀 함수는 자기 자신을 호출하는 함수를 말합니다. 쉽게 말해, 함수가 자신을 내부에서 다시 호출하는 것을 의미합니다. 이렇게 함수가 자기 자신을 호출하면서 반복적인 작업을 수행할 수 있습니다. 재귀 함수는 수학적인 문제나 복잡한 알고리즘을 간단하고 직관적으로 표현하는 데 유용합니다.
예를 들어, 팩토리얼을 구하는 문제를 재귀 함수를 사용하여 해결해보겠습니다.
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
console.log(factorial(5)); // 출력: 120위의 예시에서 factorial 함수는 자기 자신을 호출하면서 n의 값을 1씩 감소시키며 재귀적으로 팩토리얼을 계산합니다. 이렇게 재귀 함수를 사용하면 반복문을 사용하는 것보다 간결하고 직관적인 코드를 작성할 수 있습니다.
소제목: 재귀 함수의 동작 원리
재귀 함수는 자기 자신을 호출하여 작동하기 때문에 반드시 종료 조건이 필요합니다. 위의 예시에서 종료 조건은 n이 0일 때입니다. 종료 조건에 도달하면 재귀 호출이 멈추고 결과를 반환하여 재귀가 끝나게 됩니다.
재귀 함수를 호출할 때마다 함수의 호출 스택에 호출된 함수의 정보가 쌓이게 됩니다. 스택에 쌓이는 호출 정보는 메모리에 저장되며, 스택에 저장된 정보를 차례대로 처리하면서 재귀 함수가 실행됩니다. 종료 조건에 도달하지 않은 상태에서는 재귀 호출이 계속해서 일어나므로 스택에 계속 정보가 쌓이게 됩니다. 따라서 재귀 함수를 사용할 때에는 스택 오버플로우(stack overflow)를 주의해야 합니다.
소제목: 재귀 함수의 활용 예시
재귀 함수는 다양한 상황에서 유용하게 활용될 수 있습니다. 예를 들어, 피보나치 수열을 계산하는 함수를 재귀 함수로 구현해보겠습니다.
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)); // 출력: 8위의 예시에서 fibonacci 함수는 이전 두 개의 피보나치 수를 더하여 현재 피보나치 수를 계산하는 방식으로 재귀적으로 호출됩니다.
또 다른 예로는 이진 트리를 순회하는 함수를 재귀 함수로 구현할 수 있습니다. 이진 트리의 모든 노드를 순서대로 방문하기 위해 재귀적으로 왼쪽 서브트리와 오른쪽 서브트리를 순회합니다.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function traverseBinaryTree(node) {
if (node !== null) {
traverseBinaryTree(node.left);
console.log(node.value);
traverseBinaryTree(node.right);
}
}
// 이진 트리 생성
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
traverseBinaryTree(root);
// 출력:
// 4
// 2
// 5
// 1
// 3위의 예시에서 traverseBinaryTree 함수는 재귀적으로 왼쪽 서브트리를 먼저 순회한 후 현재 노드를 출력하고, 다시 재귀적으로 오른쪽 서브트리를 순회합니다. 이렇게 재귀 함수를 사용하면 이진 트리의 모든 노드를 순회할 수 있습니다.
주의해야 할 점
- 종료 조건을 반드시 설정해야 합니다. 종료 조건이 없거나 잘못 설정된 경우 무한한 재귀 호출이 발생하여 스택 오버플로우가 발생할 수 있습니다.
- 재귀 함수는 반복문과 비교하여 성능 면에서 불리할 수 있습니다. 재귀 함수는 스택에 호출 정보를 저장하고 처리하기 때문에 반복문보다 메모리를 더 많이 사용하고 실행 속도가 느릴 수 있습니다. 따라서 재귀 함수를 사용할 때는 성능에 유의해야 합니다.
- 큰 입력값에 대해서는 스택의 한계로 인해 재귀 호출이 제한될 수 있습니다. 이러한 경우에는 반복문이나 다른 방법을 고려해야 합니다.
재귀 함수는 자바스크립트에서 강력하고 유용한 기능 중 하나입니다. 이를 활용하여 문제를 해결하거나 알고리즘을 구현할 때 유용하게 사용할 수 있습니다. 하지만 재귀 함수를 사용할 때에는 종료 조건과 성능에 주의하여 적절하게 활용해야 합니다.