재귀 함수(Recursive) 예제 이분탐색, 하노이타워

재귀함수. 흐름을 잘 파악해야 합니다. 항상 return 하는 조건을 명확히 넣어주어야 합니다. 다음 아래는 이진 탐색을 재귀함수로 구현 한 것입니다.

#include <stdio.h>
 
int BSearchRecur(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 BSearchRecur(ar, first, mid - 1, target);
    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("Failed\n");
    else
        printf("target idx = %d \n", idx);
 
    idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 4);
    if (idx == -1)
        printf("Failed\n");
    else
        printf("target idx = %d \n", idx);
    return 0;
}

하노이 타워를 재귀로 구현해보겠습니다. 하노이 타워는 3개의 명령문이 재귀적으로 이루어집니다. 모든 원반이 A에 올려져 있고, 이것을 C로 옮긴다고 가정해봅시다. 1. 작은 원반 n-1개를 A에서 B로 이동 합니다. 2. 큰 원반 1개를 A에서 C로 이동합니다. 3. 작은 원반 n-1개를 B에서 C로 이동합니다.

#include <stdio.h>
 
void HanoiTowerMove(int num, char from, char by, char to) {
    if (num == 1)
    {
        printf("원반1을 %c -> %c\n", from, to);
    }
    else {
        HanoiTowerMove(num - 1, from, to, by); // 처음 3개중 위에 2개를 A에서 B로
        printf("원반 %d를 %c->%c\n", num, from, to); // 처음 제일 큰 원반을 C로
        HanoiTowerMove(num - 1, by, from, to); // 가운데 2개를 B에서 C로 옮깁니다.
    }
}
 
int main(void) {
    
    // 막대A의 원반 3개를 막대B를 경유하여 막대 C로 옮기기
    HanoiTowerMove(3, 'A', 'B', 'C');
    return 0;
}