하노이의 탑과 재귀 함수 (학교 과제, p58)

Q1. 하노이의 탑 각 단계

하노이의 탑 목표

A에 있는 원판을 모두 C로 옮기기

하노이의 탑 규칙

1. 한 번에 한 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 올려지면 안 된다.

 

위에 원판이 3개인 하노이 탑을 예로 들면

A => B

A => C

C => B

A  => C

B  =>  A

B => C

A  => C

이렇게 하면 위에 이미지 처럼 A에 있는 원판이 모두 C로 이동한다.

 

n개의 원판이 있는 하노이의 탑의 이동 횟수는

T(n) = 2^n - 1

로 나타낼 수 있다.

예)

원판이 4개 있는 하노이의 탑 이동 횟수

T(4) = 2^4 - 1 = 16 - 1 = 15

원판이 5개 있는 하노이의 탑 이동 횟수

T(5) = 2^5 - 1 = 32 - 1 = 31

 

Q2. 재귀함수란?

재귀 함수는 자기 자신을 호출하여 문제를 해결하는 함수이다.

재귀 함수는 일반적으로 다음 두 가지 구성 요소를 포함한다.

 

기본 사례(Base Case):

재귀 호출을 멈추는 조건으로,

함수가 더 이상 자신을 호출하지 않고 종료되는 경우이다.

기본 사례는 재귀가 무한히 반복되는 것을 방지한다.

재귀적 사례(Recursive Case):

함수가 자기 자신을 호출하는 부분으로,

문제를 더 작은 하위 문제로 분할하여 해결한다.

 

코드로 예시를 들겠다.

#include <stdio.h>

int fect(int);

int main(){ 
    int n, i, result=1; 

    printf("정수 입력 : "); 
    scanf("%d", &n); 

    result = factorial(n);

    printf("%d! = %d\n", n, result); 

    return 0; 
}

int factorial(int n){
    if (n == 1) // 기본 사례
        return 1;
    else
        return n * fect(n - 1); // 재귀적 사례
}

위 코드에 factorial 함수에서 n == 1일 때 기본 사례로 1을 반환한다.

그렇지 않으면 n을 n-1의 팩토리얼과 곱한 값을 반환하는 재귀 호출을 수행한다.