[자료구조 이론] 재귀(Recursion)에 대해서

재귀란? 

재귀란 자기 자신을 재참조하는 형태의 알고리즘을 의미한다.

 

재귀의 장점

1. 피보나치수열, 팩토리얼과 같이 재귀적 표현이 자연스러운 해결에 대해서는 도움이 된다.(가독성)

2. 함수를 단순하게 만들어 준다

3. 변수사용을 줄여준다.

 

재귀의 단점

1. 메모리를 많이 차지하며 성능이 반복문에 비해 느리다.(함수 스택 call이 반복적으로 이루어지므로)

2. StackOverflow가능성이 크다

3. CPU 크래쉬를 발생시키기도 한다.

 

재귀의 대표적인 예시들

 

- Factorial

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

if __name__ == "__main__":
    n = int(input("출력할 팩토리얼 값 입력하기 : "))
    print(f"{n}의 팩토리얼 값은 {factorial(n)}입니다")

- GCD(Great Common Divisor, 최대 공약수)

from typing import Any

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

if __name__ == "__main__":
    x = int(input("첫번째 정숫값을 입력하세요 : "))
    y = int(input("두번째 정숫값을 입력하세요 : "))
    print(f"두 정수 {x} {y}의 최대공약수는 {GCD(x,y)}이다.")

- 하노이의 탑

def hanoi(floor, a,b,c):
    if floor == 1:
        print(f"{floor} : {a} -> {c}")
    else:
        hanoi(floor - 1, a, c ,b)
        print(f"{floor} : {a} -> {c}")
        hanoi(floor -1 , b, a ,c)

if __name__=="__main__":
    hanoi(3,"a","b","c")

<결과>
1 : a -> c
2 : a -> b
1 : c -> b
3 : a -> c
1 : b -> a
2 : b -> c
1 : a -> c

- N-Queen

chessSize = int(input("Chess Size >>"))
totalCount = 0 # total count of queen set
col = [0] * chessSize # column info 
row = [False] * chessSize # row info
dim1 = [False] * ((chessSize * 2) - 1) 
dim2 = [False] * ((chessSize * 2) - 1)
# print queen set 
def printChess() -> None:
    for i in range(chessSize):
        print(f"{col[i] : 2}",end='')
    print()
# Get Dim1's Index
def getDim1Index(i,j):
    return i + j
#Get Dim2's Inex
def getDim2Index(i,j):
    return ((i - j) + (chessSize - 1))

def setChess(i : int) -> None:
    global totalCount
    for j in range(chessSize):
        #해당 행, 두방향의 대각선 모두에 배치가 안된 경우
        if (not row[j] and not dim1[getDim1Index(i,j)] and not dim2[getDim2Index(i,j)]): 
            col[i] = j # mean col : i ,row : j
            if i == chessSize - 1:
                totalCount += 1
                printChess()
            else:
                # j번째 행에 배치가 되지 않은 경우
                row[j] = dim1[getDim1Index(i,j)] = dim2[getDim2Index(i,j)] = True
                setChess(i + 1)
                row[j] = dim1[getDim1Index(i,j)] = dim2[getDim2Index(i,j)] =  False
        else:
            pass

setChess(0)
print(totalCount)

 

재귀 알고리즘의 분석 2가지

 

재귀 알고리즘 분석방법에는 2가지가 존재한다. 하나는 하향식분석이고 하나는 상향식 분석이다. 예를 들어 아래와 같은 코드가 있고, 이를 각 방법으로 분석해 보자. 예를 들어 4라는 값을 입력했다고 가정하면, 답은 1 - 2 - 3 - 1 - 4 - 1- 2가 될 것이다.

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

 

- 하향식 분석

하향식 분석은 가장 위쪽에 위치한 상자의 함수호출부터 시작해 계단 식으로 자세히 분석하는 방법이다. 하향식 분석은 동일한 매개변수 호출을 여러번 호출하는 경우가 발생하므로 효율적인 분석법이라고 할 수 없다.

- 상향식 분석

상향식 분석은 하향식과 달리 아래쪽부터 쌓아올리며 분석하는 방식입니다. 상향식 분석을 해보겠습니다. 우선적으로 n값이 최소 1이어야 실행이 된다는것을 알 수 있습니다. 그렇기 때문에, n값이 1일때를 기준으로 시작해 올라가 보겠습니다.

 

n = 1

recur(0)실행

1출력

recur(-1)실행

 

n =2 

recur(1) 실행

2출력

recur(0) 실행

이와 같이 계속 올라가면서 분석하면 이와 같이 표를 만들수 있습니다.

recur(1)	recur(0) 1 recur(-1)	1
recur(2)	recur(1) 2 recur(0)	1 2
recur(3)	recur(2) 3 recur(1)	1 2 3 1
recur(4)	recur(3) 4 recur(1)	1 2 3 1 4 1 2