아카이브/알고리즘

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

될성부른떡잎 2015. 10. 28. 15:22


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


Reversing Array (배열 뒤집기)

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

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


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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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 beginint end)
{
    // begin과 end가 같아지는 경우는 a의 원소의 개수가
    // 홀수일때 인데 가운데 begin, end 둘 다 가운데 값을
    // 가르키고 있으므로 바꿀 필요가 없다.
    if (begin < end)
    {
        swap(a, beginend);
        reverseRecursive(a, begin+1end-1);
    }
}
 
// 반복문 구현
void reverseLoop(int a[], int beginint end)
{
    for (int i=begin; i<(begin+end)/2++i)
    {
        swap(a, i, end-i);
    }
}
 
int main()
{
    int a[7= {1234567};
    reverseRecursive(a, 06);
    for (int i=0; i<7++i)
        cout << a[i];
    return 0;
}
cs


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

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