재귀의 활용

피보나치 수열(Fibonacci Sequence)

피보나치 수열은 앞엣것 두 개 더해서 현재의 수를 만들어가는 수열이다.

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값

따라서 피보나치 수열의 n번째 위치의 값을 반환하는 함수는 수학적으로 다음과 같이 표현이 되낟.

그럼 이를 코드로 옯겨보겠다.

int Fibo(int n) {
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return Fibo(n - 1) + Fibo(n - 2);
}

우리는 피보나치 수열을 모두 표현한 것이다. 

보통 우리는 '이 함수가 호출이 되고, 그 다음은 저 함수가 호출되네' 라고 하면서 함수의 호출순서를 파악해야 이해가 된 것 같아 한다. 하지만 우리는 피보나치 수열을 수식으로 옮긴 후 그대로 코드로 나열했는데 잘 실행된다. 호출순서를 파악하지 않아도 말이다. 

따라서 재귀함수는 함수간의 호출순서를 파악하는 것이 아닌 코드의 흐름을 파악하자

이진 탐색 알고리즘의 재귀적 구현

이진 탐색 알고리즘은 반복 패턴만 알면 쉽게 구현할 수 있다. 반복 패턴은 다음과 같다.

1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인

2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

이렇듯 위 두 단계로 정리할 수 있다. 그리고 탐색의 실패가 결정되는 시점은 '탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우'라고 할 수 있다.

이것이 바로 재귀함수의 탈출조건이 된다. 재귀함수의 탈출은 탐색 대상을 찾았거나 탐색 대상이 배열에 존재하지 않는 경우에 이뤄지기 때문이다.

위 3가지 정보를 가지고 함수를 만들면 다음과 같다.

#include<stdio.h>
 
int BSearchRecur(int ar[], int first, int last, int target);
 
int main() {
    int arr[] = { 1,3,5,7,9 };
    int idx;
 
    idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 7);
    if (idx == -1)
        printf("탐색 실패\n");
    else
        printf("타켓 저장 인덱스 : %d \n", idx);
 
    idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 4);
    if (idx == -1)
        printf("탐색 실패\n");
    else
        printf("타켓 저장 인덱스 : %d\n", idx);
 
    return 0;
}
 
int BSearchRecur(int ar[], int first, int last, int target) {
    int mid;
    if (first > last)
        return -1;                        //-1의 반환은 탐색의 실패를 의미
    mid = (first + last) / 2;            // 탐색대상의 중앙을 찾는다.
 
    if (ar[mid] == target)
        return mid;                        // 탐색된 타켓의 인덱스 값 반환
    else if (target < ar[mid])
        return BSearchRecur(ar, first, mid - 1, target);
    else
        return BSearchRecur(ar, mid + 1, last, target);    

여기서 가장 중요한 코드는 BSearchRecur 함수를 호출하는 두 함수의 호출문이다.

BSearchRecur(ar, first, mid - 1, target);
BSearchRecur(ar, mid + 1, last, target);    

위 두 함수는 mid의 값에 target이 저장되어 있지 않다면 탐색 범위를 반으로 줄여서 다시 탐색을 시작하게 한다. 

따라서 이 두 함수가 이진 탐색 알고리즘을 이뤄내게 하는 재귀의 핵심이다.

-------------------------------------------

이 글은 <윤성우의 열혈 자료구조>를 보고 정리한 글입니다.