[열혈자료구조] 2강. 재귀(Recursion)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

재귀는 자료구조와 알고리즘에서 매우 중요한 요소이다.

재귀함수의 기본적 이해

void Recursive(){
    printf("Recursive Call\n");
    Recursive();
}

재귀함수는 위와 같이 함수 안에서 함수를 다시 호출하는 형태이다. 그러나 Recursive의 정의 부분에서 Recursive를 호출하고 있는데, 정의가 끝나지 않은 함수를 다시 호출하는 것이 가능한가? 재귀함수가 작동할 때 아래와 같이 메모리상에서 함수의 복사본을 여러 개 만들고 다시 호출한다. 즉, 함수의 명령문을 실행할 때 CPU로 불러와서 사용하는데, 명령문을 실행하는 중간에 재귀 조건이 등장한다면 CPU로 하나 더 불러오면 그만이다.

 

위의 코드가 실행되지 않는 이유는 재귀의 탈출 조건이 없기 때문인데, 아래와 같이 탈출조건을 추가해보자.

#include <stdio.h>

void Recursive(int num){
    if(num<=0){
        return;
    }
    printf("Recursive call %d\n", num);
    Recursive(num-1);
}

int main(void){
    Recursive(3);
    return 0;
}

 

이를 컴파일하고 실행하면 아래와 같은 결과가 나온다.

이는 아래와 같은 순서로 작동한다.

1. Recursive(3) 호출
2. Recursive(2) 호출
3. Recursive(1) 호출
4. Recursive(0) 호출
5. if문에 의해 recursive(1)로 반환
6. if문에 의해 recursive(2)로 반환
7. if문에 의해 recursive(3)으로 반환

재귀함수의 활용

이진 탐색

 

재귀함수는 다양한 구현에 사용할 수 있는데, 대표적으로 팩토리얼(factorial)함수와 피보나치 수열 함수를 재귀적으로 정의한다. 앞선 포스팅에서 적었던 이진 탐색(Binary Search)를 재귀함수로 구현해 보자. 이진 탐색은 아래 두 과정의 반복으로 볼 수 있다.

1. 탐색 범위의 중간에 목표 값이 있는지 확인
2. 목표 값이 없다면 범위를 반으로 줄여 다시 탐색

또한 탈출 조건은 탐색 대상을 찾은 경우와 탐색 대상이 배열에 존재하지 않는 경우이다. 열혈자료구조 교재에서는 이를 아래와 같이 구현하였다.

#include <stdio.h>

int BSearch(int ar[], int first, int last, int target){
    int mid;
    if(first > last)
        return -1;
    mid = (first+last)/2;
    if(ar[mid] == target){
        return mid;
    }
    else if(target<ar[mid]){
        return BSearch(ar, first, mid-1, target);
    }
    else{
        return BSearch(ar, mid+1, last, target);
    }
}

int main(void){
    int arr[] = {1, 3, 5, 7, 9};
    int idx;
    idx = BSearch(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
    if(idx == -1){
        printf("failed search\n");
    }
    else{
        printf("index of target: %d\n", idx);
    }
    idx = BSearch(arr, 0, sizeof(arr)/sizeof(int)-1, 4);
    if(idx == -1){
        printf("failed search\n");
    }
    else{
        printf("index of target: %d\n", idx);
    }
    return 0;
}

 

BSearch 함수는 search하려는 배열(arr), search할 최소와 최대 인덱스, 그리고 target을 input으로 받는다. 최대 인덱스는 sizeof(arr)/sizeof(int)-1로 계산했는데, 여기서는 배열의 길이가 5이므로 마지막 인덱스 값인 4에 해당할 것이다.

 

또한 찾고 있는 인덱스의 중간 값(mid)를 정의하였다. (a+b)/2를 계산할 때, python에서는 a와 b가 모두 정수여도 2로 나누기 연산을 해당할 때 2.5로 자동으로 형변환을 해 주지만, C언어에서는 정수의 나눗셈 결과도 무조건 정수(2)이므로 a+b가 홀수더라도 오류가 나지 않는다.

 

만약 target이 arr[mid]와 같으면 mid가 정답이므로 반환, 그렇지 않으면 target과 arr[mid]를 크기 비교하여 절반의 데이터를 날리고 나머지 절반에서 BSearch를 다시 호출한다. 위를 실행한 결과, 첫 번째 idx는 7이 있으므로 해당하는 인덱스 3을 반환하였고, 두 번째 idx는 4가 없으므로 -1을 반환하였다.

 

실제로는, 이진 탐색 알고리즘을 재귀적으로 구현하는 것보다는 반복문으로 하는 것이 더 효율적이라고 한다.

 

하노이 타워

 

하노이 타워는 재귀함수를 대표하는 문제이다. 하노이 타워 문제는 3개의 막대가 있고, 첫 막대의 n개의 원반이 있을 때, 규칙에 맞에 n개의 원반을 모두 3번째 막대로 움직이는 방법에 관한 문제이다.

출처: 위키백과

하노이 타워 문제의 규칙은 아래와 같다.

• 원반은 한 번에 하나씩만 옮길 수 있다.
• 작은 원반의 위에 큰 원반이 올라갈 수 없다.

이 문제를 아래와 같이, 첫 번째 막대에 있는 N개의 원반을 N-1개와 1개로 나누어 생각해 보자.

먼저 N-1개의 원반을 2번째 막대로 옮긴다.

다음으로 1개의 원반을 3번째 막대로 옮긴다.

마지막으로 N-1개를 3번째 막대로 옮긴다.

이러한 과정으로 나누어 생각하면, N개의 원반을 옮기는 방법에 대한 식은 N-1개의 원반을 옮기는 방법에 대해 나타낼 수 있다. 이를 재귀적으로 아래와 같이 나누어 생각할 수 있다.

• N개의 원반 이동방법은 N-1개의 원반 이동방법으로 나타낼 수 있다.
• 1개의 원반은 그냥 1번 움직이면 된다 (탈출 조건)

열혈자료구조 교재에서는 이를 아래와 같이 구현하였다.

#include <stdio.h>

void Hanoi(int num, char from, char by, char to){
    if(num==1){
        printf("plate 1 from %c to %c\n", from, to);
    }
    else{
        Hanoi(num-1, from, to, by);
        printf("plate %d from %c to %c\n", num, from, to);
        Hanoi(num-1, by, from, to);
    }
}

int main(void){
    Hanoi(3, 'A', 'B', 'C');
    return 0;
}

 

이를 실행하면 아래와 같이 과정이 나온다.

원반의 수를 4로 바꾸어 다시 실행해 보자.