재귀 알고리즘

• 어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 재귀라고 함

재귀를 이용한 자연수의 정의

자연수의 정의

• 1은 자연수임.
• 어떤 자연수의 바로 다음 수도 자연수임

• 무한히 존재하는 자연수를 재귀적 정의를 사용해 위 두 문장으로 정의한 것.

직접 재귀와 간접 재귀

• 자기 자신을 직접 호출하는 것 : 직접 재귀
• a가 b를 호출하고 b가 다시 a를 호출 하는 것 : 간접 재귀
  

팩토리얼

** 팩토리얼(n!)의 정의

• 0! = 1
• n > 0 이면 n! = n x (n-1)!

• ex) 10! = 10 x 9! = 10 x 9 x 8! = ...

팩토리얼을 함수로 구현

def factorial(n: int) -> int:
	if n > 0:
    	return n * factorial(n-1)
    else:
    	return 1

• 위와 같은 함수의 호출을 재귀 호출 이라고 함
• 재귀함수를 설명하기 위한 예시일 뿐 팩토리얼은 재귀로 정의하지 않는 것이 효율적임

유클리드 호제법

• 두 개의 자연수의 최대공약수를 구하는 방법 중 하나
  

  1. 직사각형에서 짧은 변의 길이를 한 변으로 정사각형으로 나눔
  2. 남은 직사각형에서 똑같은 과정을 반복
  3. 마지막에 남은 정사각형의 길이가 최대 공약수임

유클리드 호제법 프로그램

def gcd(x: int, y: int) -> int:
    """정숫값 x와 y의 최대 공약수를 반환"""
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

재귀 알고리즘 분석

순수한 재귀함수

• 재귀 호출을 여러 번 실행하는 함수

def recur(n: int) -> int:
	if n > 0:
    	recur(n - 1)
        print(n)
        recur(n - 2)

x = int(input('정숫값을 입력하세요: '))

recur(x)

하향식 분석

• 위 함수의 n에 4를 전달했을 때

  recure(4) 의 실행 과정

  1. recur(3)을 실행
  2. 4를 출력
  3. recur(2)를 실행

• 위 그림처럼 가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사해 나가는 분석 방법

상향식 분석

recure(4) 의 실행 과정
1. recur(0)을 실행
2. 1을 출력
3. recur(-1)를 실행

• 하향식 분석과 반대로 아래쪽부터 쌓아 올리며 분석하는 방법

하노이의 탑

• 1,2,3번 기둥이 있을 때 n개의 원판을 1번에서 3번 기둥으로 옮기는 문제
• 1번에 1개의 원판만을 움직일 수 있음

하노이의 탑 코드 구현

def move(no: int, x: int, y: int) -> None:			# 원판 no개를 x기둥에서 y기둥으로 옮김)
	if no > 1:
    	move(no - 1, x, 6 - x - y)
        
    if no > 1:
    	move(no - 1, 6 - x - y, y)

• 기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 위치에 있든, 중간 기둥은 (6-x-y)로 구할 수 있음.

8퀸 문제

8개의 서로 공격할 수 없도록 8 * 8 체스판에 배치

퀸 배치하기

• 같은 행에 있으면 서로 공격할 수 있음
• 한 행에 하나만 배치 가능
• 첫 번째 퀸을 배치한 행(8경우의 수)을 제외한 행에 다음 퀸 배치(7경우의 수) 가능

분기 작업으로 문제 해결하기

• 배열 pos는 퀸의 배치를 나타냄
• i열에 배치한 퀸의 위치가 j행에 있으면 pos[i] = j로 나타냄
  pos[1] = 4이면 1열 4행에 퀸이 배치돼있음

pos = [0] * 8       # 각 열에서 퀸의 위치
flag = [False] * 8  # 각 행에 퀸을 배치했는지 체크

def put() -> None:
    """각 열에 놓은 퀸의 위치를 출력"""
    for i in range(8):
        print(f'{pos[i]:2}', end='')
    print()

def set(i: int) -> None:
    """i 열의 알맞은 위치에 퀸을 배치"""
    for j in range(8):
        if not flag[j]:  # j 행에 퀸을 배치하지 않았으면
            pos[i] = j   # 퀸을 j 행에 배치
            if i == 7:   # 모든 열에 퀸을 배치를 완료
                put()
            else:
                flag[j] = True
                set(i + 1)  # 다음 열에 퀸을 배치
                flag[j] = False

set(0)  # 0열에 퀸을 배치

• 불필요한 조합을 열거하지 않는 방법을 한정작업이라고 함
• 분기 작업과 한정작업을 조합하여 문제를 풀이하는 방법을 분기 한정법이라고 함

8퀸 문제 해결 프로그램

• 위 코드는 행과 열 방향으로만 겹치지 않는 조합을 나열하는 프로그램임
• 퀸은 대각선 방향도 공격가능하기 때문에, 대각선 배치 문제도 고려하면 문제가 해결됨

pos = [0] * 8          # 각 열에 배치한 퀸의 위치
flag_a = [False] * 8   # 각 행에 퀸을 배치했는지 체크
flag_b = [False] * 15  # 대각선 방향(↙↗)으로 퀸을 배치했는지 체크
flag_c = [False] * 15  # 대각선 방향( ↘↖)으로 퀸을 배치했는지 체크

def put() -> None:
    """각 열에 배치한 퀸의 위치를 출력"""
    for i in range(8):
        print(f'{pos[i]:2}', end='')
    print()

def set(i: int) -> None:
    """i 열의 알맞은 위치에 퀸을 배치"""
    for j in range(8):
        if(     not flag_a[j]            # j행에 퀸이 배치 되지 않았다면
            and not flag_b[i + j]        # 대각선 방향(↙↗)으로 퀸이 배치 되지 않았다면
            and not flag_c[i - j + 7]):  # 대각선 방향( ↘↖)으로 퀸이 배치 되지 않았다면
            pos[i] = j  # 퀸을 j행에 배치
            if i == 7:  # 모든 열에 퀸을 배치하는 것을 완료
                put()
            else:
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
                set(i + 1)  # 다음 열에 퀸을 배치
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False

set(0)  # 0열에 퀸을 배치