재귀함수 관련 알고리즘

● 유클리드 알고리즘 

유클리드 호제법이란,
A >= B인 어떤 두 정수 A와 B가 있을 때 ( A = Bq + r로 나타낼 수 있다.)
A와 B의 최대공약수 gcd(A, B) = d 는 gcd(B, r)과 같다.
즉, 쉽게 말하면 두 수의 최대공약수는 "큰 수를 작은 수로 나눈 나머지"와 "작은 수"의 최대공약수와 같다는 것이다.

int gcd(int x, int y) {
    if ( y == 0 )
        return x;
     else
        return gcd(y , x%y);
}

● 하노이의 탑

하노이 탑이란 1883년 프랑스 수학자 루카스(Lucas)에 의해 고안된 문제인데, 가운데 기둥을 이용해서 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽 기둥으로 옮기는 문제였다. 이때 원판은 한번에 한 개씩만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다는 조건이 따른다.

여기서 A는 왼쪽 기둥, B는 가운데 기둥, C는 오른쪽 기둥을 의미하고, n은 옮기고자 하는 원판의 수이다.

void hanoi(int n, char A[], char B[], char C[])
{
    if ( n== 1 )
        printf("board %d move %s -> %s", n, A, C);
    else {
        hanoi(n-1, A, C, B);
        printf("board %d move %s -> %s", n, A, C);
        hanoi(n-1, B, A, C);
    }
}