python_재귀알고리즘

재귀(recursion)

자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우

• 팩토리얼(factorial) 코드

def factorial(n : int) -> int:
    if n > 0:
        return n * factorial(n - 1)	#n! = n * (n-1)
    elif n == 0:
        return 1
    else: 					
        raise ValueError

if __name__ == '__main__':
    n = int(input('출력할 팩토리얼 값을 입력하세요.: '))
    try:
        print(f'{n}의 팩토리얼은 {factorial(n)}입니다.')
    except ValueError:	#음수일 때 예외처리
        print(f'{n}의 팩토리얼은 구할 수 없습니다.')

직접(direct) / 간접(indirect) 재귀

직접재귀: 자신과 똑같은 함수 호출

간접 재귀: a함수가 b함수를 호출하고 다시 b함수가 a함수를 호출하는 구조

• 유클리드 호제법 _ 최대공약수(GCD)

x = az, y = bz를 만족하는 정수 a,b와 최대 정수 z가 존재할 때 z는 gcd(x,y)

def gcd(x: int, y: int) -> int:
    if y == 0:					#y가 0이면
        return x				#x리턴
    else:
        return gcd(y, x % y)	#최대공약수는 x%y (나머지값)

if __name__ == '__main__':
    print('두 정숫값의 최대 공약수를 구합니다.')
    x = int(input('첫 번째 정숫값을 입력하세요.: '))
    y = int(input('두 번째 정숫값을 입력하세요.: '))

    print(f'두 정숫값의 최대 공약수는 {gcd(x, y)}입니다.')

순수재귀 (genuinely)

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

• 스택으로 재귀함수 구현

from stack import Stack

def recur(n: int) -> int:
    s = Stack(n)

    while True:
        if n > 0:
            s.push(n)         #n값을 push
            n = n - 1
            continue
        if not s.is_empty():  #스택이 비어 있지 않으면
            n = s.pop()       #저장하고 있는 값을 n에 팝
            print(n)
            n = n - 2
            continue
        break

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

recur(x)

• 하노이의 탑(towers of Hanoii)

작은 원반 위에, 큰 원반이 아래에 위치하는 규칙

3개일 때: 원반 1과 원반 2를 그룹으로 묶어 중간 기둥으로 옮긴다.

4개일 때:원반 1,2,3을 그룹으로 묶어 중간 기둥으로 옮긴다.

def move(no: int, x: int, y: int) -> None:	#no:원반개수, x:시작기둥번호, y: 목표기둥번호
    if no > 1:						#원반 개수가 1개보다 많을 때
        move(no - 1, x, 6 - x - y)	#큰 거 빼고 옮기는 것이므로 no - 1

    print(f'원반 [{no}]을(를) {x}기둥에서 {y}기둥으로 옮깁니다.')

    if no > 1:
        move(no - 1, 6 - x - y, y)	#중앙 기둥의 값 최종 기둥으로 옮긴다.

n = int(input('원반의 개수를 입력하세요.: '))

move(n, 1, 3)	#1기둥에 쌓인 원반 n개를 3기둥으로 옮긴다.