[알고리즘] 재귀란 무엇인가?

---

☑️ 재귀란 무엇인가?

드디어 블로그에 재귀를 포스팅한다. 짧은 크래프톤 정글 기간에 나를 많이 괴롭혔던 이론이다. 재귀란 무엇인가? 간단하고 쉽다. 재귀는 자기 자신을 참조하는 알고리즘이다. 어? 자기 자신을 참조한다고? 이게 무슨 의미지? 싶다면 아래 사진을 보자.

 

재귀의 이론 자체는 어렵지 않다. 정말 그대로 자기 자신을 참조하는 알고리즘이 전부이기 때문이다. 사실 프로그래머는 코드로 이해하는 게 더 빠를 수 있다. 바로 팩토리얼을 구하기 위해서 재귀를 사용한 예시를 보자.

def factorial(a : int) -> int:
    if a < 1:
        return 1
    return a * factorial(a - 1)
    
sum = factorial(5)

# 120
print(sum)

 

팩토리얼은 정수 1부터 N까지 곱한 연산을 결과로 반환한다. 수학적으로는 다음과 같이 표기하고 연산한다.

5! (5 팩토리얼) // 5 * 4 * 3 * 2 * 1

 

재귀는 쉽다. 하지만, 재귀를 도입하는 것은 어렵고 잘못 구현한다면 버퍼 오버플로우가 일어날 확률이 굉장히 높다. 심지어 재귀로 풀 수 있는 문제는 반복문으로 풀 수 있다.

 

🔍 내 생각에는..

개인적으로 게임을 개발하면서 기능 구현에 재귀 함수를 사용해서 풀어본 적은 없다. 협업 시에 코드 가독성을 고려하면 지양해야 한다고 생각한다. 나중에 정글을 수료한다면 동일하게 재귀를 사용하지는 않을 것 같다.

 

재귀를 사용하기 위해서는 종료 조건을 잘 생각해보자. 도움이 될만한 블로그 링크를 첨부해 둔다.

https://velog.io/@eddy_song/you-can-solve-recursion

 

재귀를 쉽게 사용하기 위해서는 재귀를 사용해야 하는 알고리즘 문제들을 풀면서 이해해 보자.

 

🔖 [백준/1914번] 하노이 탑

재귀 함수를 사용해서 풀 수 있는 유명한 문제 중 하나다. 게시글을 작성하면서 같이 올리고 싶었지만 다른 알고리즘 문제를 풀다가 시간이 너무 오래 지나서 일단 게시글을 올려놓고 봤다ㅎㅎ..

 

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.

 

📜 코드(Python)

def move(no, x, y):
    if no == 1 :
        print(x,y)
        return
    
    move(no - 1, x, 6 - x - y)
    print(x,y)
    move(no - 1, 6 - x - y, y)
    
n = int(input())
print(2**n-1)

if n <= 20:
    move(n, 1, 3)

 

🔍 접근 방법

옛날에 풀어본 적이 있는 문제였어서 재귀를 사용해서 접근해야 하는 것을 알고 있었다. 그렇기 때문에 다음과 같이 생각하면서 재귀 함수를 작성했다. 코드 작성 전에 생각해 본 것은 재귀는 자기 자신을 참조해서 반복적인 행동을 하는 함수이기 때문에 어떻게 종료될 것인가와 어떤 행동을 반복해야 하는가가 있었다.

1번 : (N-1)에 해당하는 기둥을 가운데로 옮긴다. 

2번 : N에 해당하는 기둥을 끝으로 옮긴다.

 

위와 같이 문제를 해결하기 위한 알고리즘을 반복하면서 값을 찾는 알고리즘이 재귀다. 지금은 하노이 탑을 위해서 게시글을 작성하는 것이 아니니까. 지금은 이 정도에서 마친다. 재귀 함수.. 어렵다.