Chap02. 재귀

- 재귀 함수는 함수의 호출 순서를 100프로 파악할 필요는 없다. 

재귀 함수는 엄청나게 많은 함수의 호출을 동반하기 때문에 오히려 혼란의 가중을 일으킨다.

 

- 수식을 => 코드로 옮긴다. 

 

이분탐색의 재귀적 구성

int BinarySearchRecur(int ar[], int first, int last, int target)
{
    if(first > last) return -1; // 실패

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

 

하노이 타워의 재귀적 해결

#include <cstdio>

void HanoiTowerMove(int num, char from, char by, char to)
{
    if(num == 1)
    {
        // 가장 작은 원반 
        printf("원반 1을 %c에서 %c로 이동\n", from, to); 
        return;
    }

    // 우선 n-1개의 원반을 A에서 B로 이동시킴 (C를 거쳐)
    HanoiTowerMove(num-1, from, to, by);
    // 맨 아래 큰 원반을 A에서 C로 이동
    printf("원반 %d를 %c에서 %c로 이동\n", num, from, to);
    // B에 있는 n-1개를 C로 이동
    HanoiTowerMove(num-1, by, from, to);
}

int main()
{
    HanoiTowerMove(3, 'A', 'B', 'C');
}

 

가장 작고 위에 있는 원반 1, 가운데 원반 2, 가장 크고 아래 있는 원반 3이 A 막대에 있다.

원반 3을 C로 옮기려면 1,2 원반 부터 B로 옮겨야 한다.

이제 원반 3을 C로 옮기고, 원반 1,2를 C로 옮긴다.

 

1. 작은 원반 n-1개를 A에서 B로 이동

2. 큰 원반 1개를 C로 이동 

3. 작은 원반 n-1개를 B에서 C로 이동 

 

즉 원반 n개를 이동하는 문제는 원반 n-1개를 옮기는 문제로 세분화된다.

원반 n-1개를 옮기는 문제는 n-2개를 옮기는 문제로 세분화된다. 

...

원반 2개를 옮기는 문제는 1개를 옮기는 문제로 세분화된다. 

 

하노이탑 백준 문제: 하노이 탑 이동 순서 

https://tose33.tistory.com/625

백준 11729. 하노이 탑 이동 순서