재귀 알고리즘

재귀는 한자로 다시 재再 돌아오다 귀歸를 씁니다. 말 그대로 함수를 재차 사용합니다.

python의 경우 최대 재귀 깊이(maximum recursion depth)가 1,000으로 일반적인 적인 계산에선 필요없지만 코테에서 유명한 dfs(깊이 우선 탐색)의 문제 경우 1000으로 해결되지 않는 경우가 대부분이기에 파이썬으로 코테를 준비하는 사람의 경 sys.setrecursionlimit() 을 처음 접하는 사람은 거의 없을거라 생각합니다 :)

 

다음은 재귀로 유명한 유클리드 호제법 문제와 풀이 입니다.

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

import sys


def gcd(x: int, y: int) -> int:
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


x, y, = map(int, sys.stdin.readline().strip().split())
gcd = gcd(x, y)
print(gcd)
print(x * y // gcd)

 

Recursion(재귀)을 사용하여 정의된 함수를 for, while과 같은 반복 제어로 변환하여 비재귀적으로 표현할 수 있습니다.

import sys


def gcd(m, n):
    while n != 0:
        t = m%n
        (m, n) = (n, t)
    return abs(m)


x, y, = map(int, sys.stdin.readline().strip().split())
gcd = gcd(x, y)
print(gcd)
print(x * y // gcd)

 

그렇게 되면 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문에 선입 후출의 스택 자료구조를 필요로합니다. 

그러면 재귀와 반복, 각각의 장단점은?

 

우선 반복의 장점은 새로 함수를 호출할 필요가 없습니다. 그렇기 때문에 context switching 비용이 발생하지 않아 재귀에 비해 속도가 빠릅니다. 또 앞서 말한 파이썬의 경우 최대 재귀 깊이를 고려하지 않아도 됩니다.

**context switching**
현재 진행하고 있는 Task(Process, Thread)의 상태를 저장하고 다음 진행할 Task의 상태 값을 읽어 적용하는 과정을 말합니다.            

재귀의 장점은 변수를 여러개 만들 필요가 없고, 코드가 간결해진다는 장점이 있습니다. 유클리드 호제법 처럼 간단의 예제의 경우 m%n 의 값을 저장할 변수 t 하나만 필요하지만 좀더 복잡한 코드의 경우 가독성을 저해할 수 있습니다. :)

 

하노이탑

https://www.acmicpc.net/problem/1914

def move(no: int, x: int, y: int) -> None:
    if no > 1:
        move(no - 1, x, 6 - x - y)
    print(x, y)
    if no > 1:
        move(no - 1, 6 - x - y, y)

n = int(input())

print(2 ** n - 1)
if n <= 20:
    move(n, 1, 3)

 

8퀸 문제

 

pos = [0] * 8
flag_a = [False] * 8
flag_b = [False] * 15
flag_c = [False] * 15

def put() -> None:
    for j in range(8):
        for i in range(8):
            print("⬛️" if pos[i] == j else '◻️', end="")
        print()
    print()
def set(i: int) -> None:
    for j in range(8):
        if ( not flag_a[j] and not flag_b[i + j] and not flag_c[i - j + 7] ):
            pos[i] = 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)​