[알고리즘] 재귀를 활용하기 좋은 상황은 언제인지에 대하여

우선 재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법이다.
재귀를 활용하는 좋은 상황은 다음과 같다.

재귀와 재귀함수란?

재귀는 프로그래밍에서 자기 자신을 호출하는 함수 또는 알고리즘의 사용을 말한다.
재귀함수는 함수내에서 자기 자신을 다시 호출하는 함수를 의미한다.

재귀함수의 주요 특징

• 자기 참조(자기 호출) : 재귀 함수는 함수 내에서 자기 자신을 호출한다. 이렇게하면 함수가 여러번 반복되어 실행된다.
• 종료조건 : 재귀함수는 종료 조건을 반드시 가져야한다. 종료 조건은 함수가 무한히 호출되지 않도록 하며 특정 조건을 만족하면 재귀 호출을 중지하고 결과를 반환한다.
• 문제 분할 : 재귀함수는 주어진 문제를 더 작은 하위 문제로 분할하여 해결한다. 하위 문제는 원래 문제와 동일한 형태를 가지지만 더 작고 간단한 버전이다.

재귀는 일부 문제를 더 직관적으로 해결할 수 있도록 도와주며, 분할 정복 알고리즘, 트리 순회, 팩토리얼 계산, 피보나치 수열 등 다양한 문제와 알고리즘에 적용된다.
그러나 재귀를 사용할때는 종료조건을 신중하게 설정하여 무한 재귀에 빠지지 않도록 주의해야한다.

1. 문제가 재귀적으로 정의될 수 잇는 경우

재귀는 주어진 문제가 더 작은 하위 문제로 나누어질 수 있는 경우에 유용하다.
하위 문제들은 원래 문제와 동일한 형태를 가지며, 더 작고 간단한 버전이다.
이런 문제들은 재귀함수를 통해 해결할 수 있다.

팩토리얼 계산

팩토리얼 계산은 n! = n * (n-1) * (n-2) * ... * 2 * 1로 정의된다.
이런 정의로부터 팩토리얼은 재귀적으로 계산할 수 있다.

function factorial(n) {
  // 종료 조건: n이 0 또는 1일 때, 팩토리얼 값은 1입니다.
  if (n === 0 || n === 1) {
    return 1;
  } else {
    // 재귀 호출: n! = n * (n-1)!
    return n * factorial(n - 1);
  }
}

// 예제: 5! 계산
const result = factorial(5);
console.log(result); // 출력: 120

위 예제코드는 팩토리얼 계산을 위한 함수를 만들고 5!의 값을 출력하는 코드이다.

2. 트리 구조를 다룰 때

트리 구조는 재귀적으로 표현된다.
트리의 각 노드는 하위 트리로 구성되며, 각 하위 트리도 또 다른 트리이다.
재귀를 사용하면 트리를 순회하거나 트리 기반의 문제를 해결하는 데 효과적이다.

이진트리 순회

이진트리의 각 노드를 방문하고자 할 때, 재귀적으로 루트 노드의 왼쪽 하위 트리와 오른쪽 하위 트리를 순회할 수 있다.

1. 전위 순회(Preorder Traversal) 방법
   전위 순회 방법은 루트 노드를 먼저 방문한 후, 왼쪽 하위 트리와 오른쪽 하위 트리를 재귀적으로 순회한다.

// 이진 트리의 각 노드를 나타내는 클래스
class TreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

// 전위 순회 함수
function preorderTraversal(node) {
  if (node === null) {
    return; // 노드가 비어있으면 종료
  }

  console.log(node.data); // 현재 노드의 데이터 출력
  preorderTraversal(node.left); // 왼쪽 하위 트리 순회
  preorderTraversal(node.right); // 오른쪽 하위 트리 순회
}

// 이진 트리 생성
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// 전위 순회 호출
console.log("전위 순회 결과:");
preorderTraversal(root);

위 예제코드에서 preorderTraversal함수는 전위 순회를 수행하는 함수이다.
이 함수는 루트 노드를 방문하고, 왼쪽 하위트리를 순회한 뒤에 오른쪽 하위 트리를 순회한다.
preorderTraversal함수를 호출하면 이진 트리의 모든 노드를 전위 순회 순서로 출력할 수 있다.

2. 중위 순회(Inorder Traversal) 방법
   중위 순회는 왼쪽 하위트리를 먼저 순회한 후 현재 노드를 방문하고, 마지막으로 오른쪽 하위 트리를 순회하는 방법이다.

// 중위 순회 함수
function inorderTraversal(node) {
  if (node === null) {
    return;
  }

  inorderTraversal(node.left); // 왼쪽 하위 트리 순회
  console.log(node.data); // 현재 노드의 데이터 출력
  inorderTraversal(node.right); // 오른쪽 하위 트리 순회
}

// 중위 순회 호출
console.log("중위 순회 결과:");
inorderTraversal(root);

위 예제코드에서 inorderTraversal 함수는 중위 순회를 수행한다.

3. 후위 순회(Postorder Traversal) 방법
   후위 순회 방법은 왼쪽 하위 트리를 먼저 순회한 후 오른쪽 하위 트리를 순회하고 마지막으로 현재 노드를 방문하는 방법이다.
   함수를 호출하면 해당 중위 순회 방법에 따라 이진 트리의 노드를 방문할 수 있다.

// 후위 순회 함수
function postorderTraversal(node) {
  if (node === null) {
    return;
  }

  postorderTraversal(node.left); // 왼쪽 하위 트리 순회
  postorderTraversal(node.right); // 오른쪽 하위 트리 순회
  console.log(node.data); // 현재 노드의 데이터 출력
}

// 후위 순회 호출
console.log("후위 순회 결과:");
postorderTraversal(root);

위 예제코드에서 postorderTraversal함수는 후위 순회를 수행한다.
함수를 호출하면 해당 후위 순회 방법에 따라 이진 트리의 노드를 방문할 수 있다.

트리구조란?

트리구조(Tree Structure)는 계층적으로 데이터를 구성하는 방법 중 하나로, 그래프의 특수한 형태이다.
트리 구조는 다음과 같은 특징을 가지고 있다.

• 계층적 구조 : 트리는 계층적인 구조를 가진다. 최상위 노드를 루트(root)라고 하며, 루트에서부터 시작하여 하위 노드로 내려가며 데이터를 구성한다.
  각 노드는 부모(parent)노드와 하위(child)노드로 연결된다.
• 방향성 : 트리는 방향성을 가진다. 각 노드는 한 개 이상의 부모에 의해 참조될 수 있지만, 부모에게서 자식으로의 참조는 일방향이다.
• 사이클 없음 : 트리는 사이클(cycle)을 가지지 않는다. 다시말해 어떤 경로를 따라 이동해도 한 노드를 두번이상 방문하지 않는다.
• 하위 트리 : 각 노드는 그 하위에 또 다른 트리 구조를 형성할 수 있다. 이를 하위 트리(subtree)라고 부르며, 하위 트리는 독립적인 트리 구조이다.

트리 구조는 다양한 분야에서 사용되며, 주로 데이터 구조, 계층적인 정보 표현, 그래프 알고리즘, 컴퓨터 과학의 다양한 문제 해결에 활용된다.
일반적으로는 트리는 이진트리(Binary tree), 이진탐색트리(Binary Search Tree), 힙(heap), AVL트리, 레드-블랙 트리 등 다양한 종류의 트리가 있으며, 각각 다른 목적에 맞게 설계되어 사용된다.

이진트리란?

이진트리(Binary Tree)는 트리 구조 중 하나로, 각 노드가 최대 두개의 하위 노드를 가지는 구조를 말한다.
이진 트리는 각 노드의 왼쪽 하위 노드와 오른쪽 하위 노드로만 구성되며, 각 노드는 부모 노드와 연결되어 계층적으로 구성된다.
이진 트리는 다음과 같은 특징을 가진다.

• 루트 노드 : 트리의 맨 위에 있는 노드를 루트 노드라고 한다. 이진 트리의 모든 경로는 루트 노드에서 시작하여 루트 노드로 끝난다.
• 노드 : 트리 내 각 요소를 노드라고 부른다. 각 노드는 데이터를 저장하고, 왼쪽과 오른쪽 두개의 하위 노드를 가질 수 있다.
• 하위 트리 : 각 노드는 왼쪽 하위 트리와 오른쪽 하위 트리로 구분된다. 이 하위 트리 역시 이진트리일 수 있으며, 재귀적으로 이진 트리의 성질을 가진다.

이진트리는 다양한 형태로 활용된다.
예를 들어 이진탐색트리는 데이터를 효과적으록 검색, 삽입, 삭제하기 위한 자료구조로 사용된다.
힙은 우선순위 큐와 같은 응용에서 사용된다.

이진 탐색 트리란?

이진 탐색 트리(Binary Search Tree)는 이진 트리의 일종으로 데이터를 효율적으로 검색, 삽입, 삭제하기 위한 자료구조이다.

이진 탐색 트리의 특징을 알아보자

• 이진 트리 구조 : 이진 탐색 트리는 각 노드가 최대 두개의 하위노드(왼쪽 하위 트리와 오른쪽 하위 트리)를 가지는 이진 트리이다.
• 정렬된 구조 : 이진 탐색 트리의 노드는 왼쪽 하위 트리의 모든 노드보다 작거나 같은 값이며, 오른쪽 하위 트리의 모든 노드보다 큰 값을 가진다. 이로 인해 트리 내의 데이터는 정렬된 순서로 저장된다.
• 효율적인 검색 : 이진 탐색 트리는 데이터를 검색하는데 매우 효율적이다. 이진 탐색 알고리즘을 활용하여 데이터를 빠르게 찾을 수 있다. 루트 노드에서 시작하여 비교를 통해 이동하면서 원하는 데이터를 찾을때까지 탐색한다.
• 효율적인 삽입 및 삭제 : 데이터의 삽입과 삭제도 효율적으롯 수행된다. 데이터를 삽입할때는 정렬된 위치에 노드를 삽입하고, 삭제할 때는 정교한 알고리즘을 사용하여 노드를 삭제한다.
• 균형 탐색 트리 : 이진 탐색 트리는 트리의 균형을 유지하기 위한 여러 변형이 있다.

이진 탐색 트리는 정렬된 데이터의 검색과 관리에 매우 유용하며, 데이터 베이스 시스템, 자료구조 라이브러리, 컴퓨터 과학의 다양한 알고리즘에서 활용된다.
그러나 트리의 균형을 유지하지않으면 성능이 저하될 수 있으므로 균형 잡힌 이진 탐색 트리를 사용하는 것이 일반적이다.

이진트리와 이진 탐색 트리의 차이점

이진트리와 이진 탐색 트리의 주요 차이점은 데이터의 저장 및 정렬방식에 있다.

이진 트리는 단순히 각 노드가 최대 두개의 하위 노드를 가지는 트리 구조를 의미하고 데이터 정렬 순서에 대한 제약이 없다.
하지만 이진 탐색 트리는 데이터 정렬을 중요시하며, 왼쪽 하위 트리의 모든 노드가 현재 노드보다 작거나 같은 값을,
오른쪽 하위 트리의 모든 노드가 현재 노드보다 큰 값을 가지도록 구성된다. 이로 인해 데이터 검색 및 관리에 있어 유용한 자료구조이다.

3. 문제를 더 작은 부분 문제로 분할할 때

재귀는 분할 정복(Divide and Conquer) 알고리즘에서 주로 사용된다.
큰 문제를 작은 부분 문제로 나누어 해결한 다음, 이 부분 문제의 해결방법을 결합하여 전체 문제를 해결한다.

합병 정렬(Merge Sort)

합병 정렬은 배열을 두 개의 배열로 분할하고, 각 부분 배열을 정렬한 다음 병합하여 정렬된 배열을 생성하는 분할 정복 알고리즘이다.

// 두 개의 정렬된 배열을 병합하는 함수
function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // 두 배열을 비교하여 작은 값을 결과에 추가
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 남은 요소들을 결과에 추가
  return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

// 합병 정렬 함수
function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr; // 배열이 비어있거나 하나의 요소만 있는 경우 정렬할 필요 없음
  }

  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle); // 배열을 반으로 나눔
  const right = arr.slice(middle);

  // 재귀적으로 부분 배열을 정렬하고 병합
  return merge(mergeSort(left), mergeSort(right));
}

// 테스트용 배열
const unsortedArray = [38, 27, 43, 3, 9, 82, 10];

// 합병 정렬 호출
const sortedArray = mergeSort(unsortedArray);

console.log("정렬된 배열:", sortedArray);

배열을 반으로 나눈 뒤, 각 부분 배열을 재귀적으로 정렬하고, 정렬된 부분 배열을 병합하는 것이다.
위 코드에서 merge함수는 두개의 정렬된 배열을 병합하는 역할을 하고 mergeSort함수는 합병 정렬을 수행한다.
합병 정렬은 입력 배열을 반으로 나눈 뒤 재귀적으로 정렬하고, 정렬된 부분 배열을 병합하여 최종 정렬된 배열을 반환한다.

합병 정렬이란?

합병 정렬(Merge Sort)은 안정적인 정렬 알고리즘 중 하나로, 분할 정복 방식을 사용하여 배열을 정렬하는 알고리즘이다.
합병 정렬은 다음과 같은 주요 단계로 동작한다.

• 분할(Devide) : 정렬할 배열을 반으로 나눈다. 이 과정은 배열을 두개의 부분배열로 분할하는 것을 의미한다.
• 정복(Conquer) : 분할된 부분 배열을 재귀적으로 정렬한다. 즉, 각각의 부분 배열에 합병 정렬을 적용한다.
• 병합(Merge) : 정렬된 부분 배열을 병합하여 최종 정렬된 배열을 생성한다. 이때 두 부분 배열을 비교하면서 정렬된 순서로 합친다.

합병 정렬은 안정적인 정렬 알고리즘으로, 원래 배열의 순서를 유지한다.
또한 최악의 경우에도 시간 복잡도가 매우 효율적이다.
이 특성으로 인해 합병 정렬은 대용량 데이터를 정렬할 때 자주 사용되며 대부분의 프로그래밍 언어와 라이브러리에서 지원하고 있다.

합병정렬의 주요 장점은 안정성과 효율성이다. 하지만 메모리를 추가적으로 사용하여 부분 배열을 저장해야 하므로 공간 복잡도가 높을 수 있다.
이를 보완하기 위해 다양한 최적화 기법이 사용되기도 한다.

정리

재귀를 사용할 때는 재귀 종료 조건을 정확하게 고려해야한다.
재귀 함수는 자기자신을 계속 호출하므로 종료 조건을 명시하지 않으면 무한 반복에 빠질 수 있다.

재귀를 적절히 활용하면 코드를 간결하게 작성하고, 일부 문제를 보다 직관적으로 해결할 수 있다.
그러나 재귀가 항상 최적의 선택은 아니며, 반복문을 사용하는 것이 성능면에서는 더 효율적인 경우도 있으므로 문제의 성격과 상황을 고려하여 선택해야 한다.