[재귀 알고리즘] Reverse Array (배열 뒤집기)

[재귀 알고리즘] Reverse Array (배열 뒤집기)

Reversing Array (배열 뒤집기)

주어진 배열 $ [x_1, ... , x_n] $을 $ [x_n, ... , x_1] $로 바꾸는 것이 목적이다.

재귀의 개념을 이해하기 쉬운 예제라 재귀로 구현했지만 반복문으로 구현하는게 훨씬 효율적이다.

처음에는 1(a[0])과 7(a[6])을 바꾸고 2(a[1])와 6(a[5])를 바꾸는 함수를 호출한다.

순차적으로 진행하다가 두 점이 만나거나 교차되면 종료한다.

#include <iostream>
using namespace std;
 
void swap(int arr[], int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
// 재귀 구현
void reverseRecursive(int a[], int begin, int end)
{
    // begin과 end가 같아지는 경우는 a의 원소의 개수가
    // 홀수일때 인데 가운데 begin, end 둘 다 가운데 값을
    // 가르키고 있으므로 바꿀 필요가 없다.
    if (begin < end)
    {
        swap(a, begin, end);
        reverseRecursive(a, begin+1, end-1);
    }
}
 
// 반복문 구현
void reverseLoop(int a[], int begin, int end)
{
    for (int i=begin; i<(begin+end)/2; ++i)
    {
        swap(a, i, end-i);
    }
}
 
int main()
{
    int a[7] = {1, 2, 3, 4, 5, 6, 7};
    reverseRecursive(a, 0, 6);
    for (int i=0; i<7; ++i)
        cout << a[i];
    return 0;
}

재귀 함수를 사용할 때에는 base case 혹은 종료 조건을 잘 설정해 줘야 한다.

설정이 잘못되어 있으면 과도한 함수 호출로 인한 스택 오버플로우로 프로그램이 비정상 종료 되기 때문이다.