재귀 알고리즘, 하노이의 탑

재귀

재귀 알고리즘(Recursion)은 함수 내에서 자기 자신을 호출하여 문제를 해결하는 기법이다. 이를 통해 복잡한 문제를 단순한 방법으로 해결할 수 있다. 대표적인 예시로는 피보나치 수열, 팩토리얼 계산 등이 있다.

재귀 알고리즘은 크게 두 가지로 나뉜다. 첫 번째는 기저 사례(Base case)가 있는 경우로, 함수가 호출될 때마다 문제가 작아져서 결국 기저 사례에 도달하게 됩니다. 두 번째는 기저 사례가 없는 경우로, 함수가 무한히 호출될 수 있다. 따라서 이 경우에는 호출 횟수를 제한하는 방법이 필요하다.

def recursive_function(n):
    if n == 0:  # 기저 사례: n이 0일 때
        return 1
    else:
        return n * recursive_function(n - 1)  # 자기 자신을 호출하면서 문제를 작게 만듦

재귀 알고리즘을 사용할 때에는 함수가 호출될 때마다 스택에 쌓이는 메모리 공간을 고려해야 한다. 호출 횟수가 많은 경우에는 스택 오버플로우(Stack overflow)가 발생할 수 있다. 따라서 재귀 알고리즘을 사용할 때에는 호출 횟수를 제한하는 방법이 필요하다.

# 최대 공약수 구하기
def gcd(n1, n2):
    if n1 < n2: # n1이 n2보다 작은 경우, 두 값을 바꿔줌
        n1, n2 = n2, n1
    
    r = n1 % n2 # n1을 n2로 나눈 나머지를 계산
    
    if r == 0: # 나머지가 0이면 n2가 최대공약수이므로 n2 반환
        return n2
    else: # 나머지가 0이 아니면, n2와 r의 최대공약수를 계산

---

하노이의 탑

하노이의 탑(Hanoi Tower)은 수학적 퍼즐이자 게임으로, 기둥과 크기가 서로 다른 디스크가 세 개의 기둥에 꽂혀있는 것을 이동시켜서 다른 기둥으로 모두 옮기는 문제이다. 이 문제는 재귀 알고리즘을 이해하고 구현하는데 매우 유용한 대표적인 예시 중 하나이다.

규칙 :

• 한 번에 하나의 디스크만 이동할 수 있다.
• 어떤 디스크도 작은 디스크 위에 올려놓을 수 없다.
• 모든 디스크는 세 개의 기둥 중 하나에 꽂혀있어야 한다.

하노이의 탑 문제를 해결하는 가장 간단한 방법은 재귀 알고리즘을 사용하는 것이다. 재귀 알고리즘을 이용하면 이 문제를 간단하게 풀 수 있다. 문제를 푸는 방법은 다음과 같다.

• n-1개의 디스크를 기둥 2로 옮긴다.
• 1개의 디스크를 기둥 3으로 옮긴다.
• n-1개의 디스크를 기둥 1로 옮긴다.

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print("Move disk 1 from", source, "to", target)
        return
    hanoi(n-1, source, auxiliary, target)
    print("Move disk", n, "from", source, "to", target)
    hanoi(n-1, auxiliary, target, source)

# 사용 예시
hanoi(3, 'A', 'C', 'B')

'''
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
'''