🍒 재귀 (Recursion) (1)

 

<함수의 재귀적 호출의 이해>

재귀 함수는 알고리즘과 자료 구조 뿐 만 아니라 프로그래밍 전반에 있어 매우 중요한 기법입니다.

'하노이 타워' 와 같이 복잡해 보이는 문제 들도 재귀 함수를 이용하여 쉽게 풀리는 경우가 많기 때문에 

"강력하다" 라는 표현을 쓰게 됩니다.

 

▶ 재귀 함수란 다음과 같이 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다.

void Recursive(void)
{
    printf("Recursive call!\n");
    Recursive( );
}

Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 됩니다.

 

그러나 위와 같이 계속 호출되는 함수는 무한히 반복되는 문제가 있습니다.

▶ 따라서 '재귀 함수의 탈출 조건'을 꼭 같이 작성해주어야 합니다.

void Recursive(int num) {
    if (num <= 0)
        return;

    printf("Recursive call! %d \n", num);
    Recursive(num - 1);
}

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

Recursive 함수에서 파라미터로 받는 num 이 0보다 같거나 작을 때 Recursive 함수를 종료하는 조건을 작성해주었습니다.

 

탈출 조건을 구성한 Recursive 함수의 호출과정

위의 그림에서 보이듯이 재귀적으로 호출이 이뤄지고 있으면서

탈출 조건인 (num <= 0) 이 성립되자 함수가 반환되기 시작합니다. 

 

그렇다면 재귀 함수에서 주의해야 할 점이 '탈출 조건' 뿐 일까요?

 

▶ 재귀 함수의 호출 과정에서 '사이클'이 없어야 합니다.

사이클은 재귀 호출이 연쇄적으로 이루어지는 과정에서 같은 ‘상태’를 가진 채로 호출되는 경우를 말합니다.

쉽게 말하면 f(x)가 다시 f(x)를 호출하거나, f(x)가 f(y)를 호출한 뒤 f(y)가 다시 f(x)를 호출하는 것입니다.

계속해서 같은 상태로 호출이 된다면, 탈출 조건을 설정하더라도 탈출 조건에 도달하지 못해 무한 반복이 될 수 있습니다.

 

👉 재귀 함수 주의할 점 👈

 

1. 탈출 조건 설정

2. 사이클이 있는지 확인 

 

 

 

<재귀의 활용>

📌 피보나치 수열 : Fibonacci Sequence

피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열입니다.

0 , 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

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

 

이를 코드로 옮겨 보면,

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

int main(void)
{
    int i;
    for(i = 1; i < 15; i++)
        printf("%d ", Fibo(i));

    return 0;
}

실행 결과

함수가 어떻게 실행되고 어떤 반환 값을 가지면서 종료가 되는지 궁금할 수도 있습니다.

하지만... 정신 건강상 재귀 함수를 잘 정의했다고 믿고 코드를 짜시는 것을 추천드립니다.

 

Fibo (7) 값을 구하려면 무려 25번의 함수 호출이 이뤄진다는 사실... 

 

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

Chapter 01 에서 구현한 이진 탐색 알고리즘을 재귀함수 기반으로 재 구현하고자 합니다.

 

이진 탐색 알고리즘도 탐색 대상을 찾을 때까지 동일한 패턴을 반복하기 때문에 

재귀함수로 구현이 가능합니다.

 

먼저 이진 탐색 알고리즘의 반복 패턴을 정리해보면,

 

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

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

 

재귀 함수의 탈출 조건은

 

" 탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우 " 

 

위 정보들을 가지고 BSearchRecur 함수를 만들어 보겠습니다.

 

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; // 탐색 성공, mid 값 반환
    else if (target < ar[mid])
        return BSearchRecur(ar, first, mid - 1, target); // target과 ar[mid]값이 다르다면, 더사 함수 호출
    else
        return BSearchRecur(ar, mid + 1, last, target);
}

 

만든 함수를 적용해볼까요?

int main(void) {
    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;
}

실행 결과