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

2024. 9. 14. 16:35·공부/알고리즘


☑️ 재귀란 무엇인가?

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

 

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

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

 

야, 너두 재귀할 수 있어: 재귀가 풀리는 4단계 접근법

재귀를 쉽게 푸는 방법은 재귀적으로 생각하지 않는 것이다. 4단계로 나눠서 생각하면 끝없는 재귀를 머릿속에 그리지 않고도 재귀를 풀 수 있다!

velog.io

 

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

 

🔖 [백준/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에 해당하는 기둥을 끝으로 옮긴다.

 

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

 

 

'공부 > 알고리즘' 카테고리의 다른 글

[알고리즘] C++로 이해하는 DFS와 BFS  (0) 2025.04.03
[알고리즘] 위상정렬(Topology Sort)  (1) 2024.10.11
[알고리즘] LCS(Longest Common Subsequence)  (0) 2024.10.07
[알고리즘] 백트래킹(Backtracking)  (1) 2024.09.14
[알고리즘] #1. A* 알고리즘을 알아보자  (2) 2024.06.14
'공부/알고리즘' 카테고리의 다른 글
  • [알고리즘] 위상정렬(Topology Sort)
  • [알고리즘] LCS(Longest Common Subsequence)
  • [알고리즘] 백트래킹(Backtracking)
  • [알고리즘] #1. A* 알고리즘을 알아보자
태역
태역
  • 태역
    RYULAB
    태역
  • 전체
    오늘
    어제
    • 분류 전체보기 N
      • 언어
        • C
        • C++
        • C#
      • 엔진, 프레임워크
        • Unity
        • Unreal
        • Electron
      • 공부 N
        • 디자인 패턴
        • 수학 N
        • CS
        • Git
        • 알고리즘
        • 자료구조
      • 코테
        • 프로그래머스
        • 백준
      • 독서
        • Effective C#
        • CLR via C#
        • 뇌를 자극하는 윈도우즈 시스템 프로그래밍
        • 오브젝트
        • CSAPP
        • OSTEP
      • 프로젝트
        • Unity
      • 개발 일지
        • 퓨처리티
        • 골든타임
      • 활동
        • 게임잼 후기
        • 게임제작동아리 브릿지
        • 크래프톤 정글
        • 기타
      • 기타
  • 블로그 메뉴

    • 링크

    • 공지사항

      • 2024 04 17
    • 인기 글

    • 태그

      인프런 #인프런강의후기 #게임개발 #게임개발강의 #인강후기 #강의후기 #게임개발자 #인프런강의
      오블완
      티스토리챌린지
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    태역
    [알고리즘] 재귀란 무엇인가?
    상단으로

    티스토리툴바