Designing Recursion(재귀 설계)

순환 알고리즘의 설계

아직 내 뇌가 절차적인 방식에서 벗어나지 못한듯하다.. 뭔가 귀납적으로 설계해야함을 알면서도 재귀함수를 타고타고 내려가다 정신을 놓치기 빈번했다..

그래서 공부가 필요함을 느꼈고 재귀를 설계할 때 좋은 요령을 포스팅 하려고한다.

---

재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법이다. 재귀함수가 성립되려면 기본적으로 아래와 같은 요구사항이 있다.

재귀의 기본적인 요구조건

1. 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야한다.
2. 모든 case는 결국 bse case로 수렴해야한다.

재귀가 아닌 함수를 재귀적으로 바꿔줄 때나, 재귀함수를 설계할 때 다음 요령을 익혀두면 재귀를 설계하기가 수월해 질 수 있다.

암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔라!

즉, 매개변수를 명시화 하라는 것이다. 암시적, 명시적 매개변수가 모호할 수 있는데, 다음 예시를 보면서 설명하겠다. 참고로 c언어를 공부하고 있기에 예시는 c로 작성할 것이다.

int search(int data[], int n, int target)
{
    for (int i = 0; i < n, i++)
    {
        if (data[i] == target)
        {
            return i;
        }
        return -1;
	}
}

위 예시는 배열을 0부터 n-1까지 탐색하면서 target이 배열 어디에 있는지 찾는 함수이다. 여기서 마지막 인덱스 n은 함수의 매개변수로 줌으로써 명시적으로 표현되어있다고 할 수 있다. 하지만 시작 인덱스 0은 매개변수로써 생략되어있다. 이는 암시적으로 표현된 매개변수라 할 수 있다.

이 함수에 암시적으로 표현된 매개변수를 명시적으로 바꿔보자.

int search(int data[], int begin, int end, int target)
{
    if (begin > end) return -1;
    else if (target == data[begin]) return begin;
    else return search(data, begin+1, end, target);
}

이 함수는 시작 인덱스를 begin이라는 매개변수로 명시적으로 표현한 것을 볼 수 있다.

이것은 배열의 크기가 얼마이든 이 함수는 배열에서 begin과 end사이의 구간에서만 target을 찾을 것이란 의미이며 begin의 앞과 end 이후는 신경쓰지 않겠다는 것이다.

그리고 재귀함수의 기본적인 요구조건을 만족하기 위해 base condition을 begin이 end보다 클때는 즉, 값을 찾을수 없는 경우에는 -1을 반환하도록 했다.

그리고 위 순차탐색을 다른 방법으로도 작성 할 수 있다.

int search(int data[], int begin, int end, int target)
{
    if (begin > end) return -1;
    else
    {
        int middle = (begin+end)/2;
        if (data[middle] == target)
        {
            return middle;
        }
        int index = search(data, begin, middle-1, target);
        if (index != -1)
        {
            return index;
        } else
        {
            return search(data, middle+1, end, target);
        }	
    }
}

다른 예시로 최대값을 찾는 함수를 보자

#define max(x, y) (x) > (y) ? (x) : (y)

int find_max(int data[], int begin, int end)
{
    if (begin == end)
        return data[begin];
    else
        return max(data[begin], find_max(data, begin+1, end));
}

이 함수 또한 시작 인덱스와 끝 인덱스를 명시적으로 표현했다. 그리고 해당 함수의 base condition은 배열의 사이즈가 1일 경우이며 이 때는 그 정수의 값이 최대값이된다. 그리고 begin과, begin 다음부터 end 까지 비교해서 큰 값을 찾는것이다. 즉 첫번째 값과 그 나머지의 최댓값을 비교하는것이다.

이번에는 이진검색을 재귀로 구현해보자.

이진검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 오름차순으로 정렬하기 때문에 가운데를 기준으로 왼쪽은 기준값보다 작은값만 있으며, 오른쪽에는 기준값보다 큰 값만 위치하게 된다. 동작 방식은, 처음 중간의 값을 임의의 값으로 선택하여 그 값과 찾고자 하는 값의 크고 작음을 비교하는데, 처음 선택한 중앙값이 만약 찾는 값보다 크면 기준값의 오른쪽부터 이진탐색을 다시 시작하고 작으면 그 값의 왼쪽부터 이진탐색을 다시 시작한다.

구현한 코드는 다음과 같다.

int binary_search(int items[], int target, int begin, int end)
{
    // 시작 인덱스가 끝 인덱스보다 크다는것은 값을 찾지 못했다는 의미
    if (begin > end)
        return -1;
    else
    {
        int middle = (begin+en)/2;	
        if (items[middle] == target)
            return middle;
        else if (items[middle] < target)
            return binary_search(items, target, begin, middle-1);
        else
            return binary_search(items, target, middel+1, end);
    }
	
}

코드를 보면 가운데 값을 기준으로 타겟보다 작으면 왼쪽으로 크면 오른쪽으로 재귀적으로 탐색하는 것을 볼 수 있다.

이렇듯 재귀는 코드를 간결하게 해주는 장점이 있으며, dfs같은 알고리즘에서 빈번히 쓰임으로 설계하는 방법을 알아두면 좋을것이다!!