재귀(Recursive)란?

---

위 그림과 같이 엘레베이터에서 양옆에 거울이 있으면 이런식으로 보인다. 큰 거울 안에 작은 거울이, 그 안에 또 작은 거울이 있다. 하지만 실제로는 언젠가는 너무 작아져서 더 이상 볼 수 없게 되는 순간이 온다. 그게 재귀에서의 종료 조건(멈추는 지점)이다

재귀에서 가장 유명한 사용 예시는 바로 팩토리얼이다
팩토리얼이란 숫자들을 차례대로 곱한다. 예를 들어, 5! = 5 * 4 * 3 * 2 * 1 = 120 이렇게 된다. 이를 재귀로 쉽게 표현할 수 있다.

1. 기본 조건: 1! = 1 (1일 때는 결과가 그냥 1)
2. 재귀 호출: n! = n * (n-1)! (n이 1보다 클 때는 자기 자신을 다시 호출)

int factorial(int n) {
    // 기저 조건: n이 1이면 1을 반환
    if (n == 1) return 1;
    // 재귀 호출: n * (n-1)!
    return n * factorial(n - 1);
}

이것의 동작 방식은 다음과 같아요. 예를 들어, factorial(5)를 호출한다고 하면 다음과 같이 된다.

1. factorial(5)는 5 * factorial(4)를 계산하려고 함.
2. factorial(4)는 4 * factorial(3)을 계산하려고 함.
3. factorial(3)는 3 * factorial(2)을 계산하려고 함.
4. factorial(2)는 2 * factorial(1)을 계산하려고 함.
5. factorial(1)은 1이니까 더 이상 계산하지 않고, 이 값을 위로 전달함.
6. 각 계산을 차례로 마쳐서 최종적으로 5 * 4 * 3 * 2 * 1 = 120이 됨!

재귀를 이용해서 퀵 정렬을 이용해보자.

퀵 정렬

---

#include <iostream>
#include <vector>
using namespace std;

void QuickSort(vector<int>& arr, int low, int high) {
    if (low >= high) return;

    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    int pi = i + 1;

    QuickSort(arr, low, pi - 1);
    QuickSort(arr, pi + 1, high);
}
int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};

    QuickSort(arr, 0, arr.size()-1);
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

퀵 정렬(quick sort) 알고리즘의 개념 요약

• ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘
• 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
• 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
  • 분할 정복(divide and conquer) 방법
  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
    분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
• 과정 설명
  1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
  2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
  3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
  4. 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
  5. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
  6. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
  7. 리스트의 크기가 0이나 1이 될 때까지 반복한다.
     

퀵 정렬(quick sort) 알고리즘의 구체적인 개념

• 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 퀵 정렬은 다음의 단계들로 이루어진다.
  • 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
  • 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
  • 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
  • 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
    

퀵 정렬(quick sort) 알고리즘의 예제

• 배열에 5, 3, 8, 4, 9, 1, 6, 2, 7이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

• 퀵 정렬에서 피벗을 기준으로 두 개의 리스트로 나누는 과정(c언어 코드의 partition 함수의 내용)

• 

• 피벗 값을 입력 리스트의 첫 번째 데이터로 하자. (다른 임의의 값이어도 상관없다.)

• 2개의 인덱스 변수(low, high)를 이용해서 리스트를 두 개의 부분 리스트로 나눈다.

• 1회전: 피벗이 5인 경우,

  1. low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗보다 큰 데이터(8)을 찾으면 멈춘다.
  2. high는 오른쪽에서 왼쪽으로 탐색해가다가 피벗보다 작은 데이터(2)를 찾으면 멈춘다.
  3. low와 high가 가리키는 두 데이터를 서로 교환한다.
  4. 이 탐색-교환 과정은 low와 high가 엇갈릴 때까지 반복한다.

• 2회전: 피벗(1회전의 왼쪽 부분리스트의 첫 번째 데이터)이 1인 경우,

  • 위와 동일한 방법으로 반복한다.

• 3회전: 피벗(1회전의 오른쪽 부분리스트의 첫 번째 데이터)이 9인 경우,

  • 위와 동일한 방법으로 반복한다.