[Problem Solving] 재귀함수 개념 및 백준 예제/Python

해당 게시글은 비전공자이자 쌩초보 개발자 지망생이 작성한 글로 정확하지 않을 수 있으니 참고해주시길 바랍니다! 

피드백과 정보 정정 댓글은 환영입니다 :)

 

재귀 함수의 정의를 구글에 찾아보면 '어떠한 것을 정의할 때 자기 자신을 참조하는 것'이라는, 이해가 될 듯하면서 되지 않을 듯한 문장을 볼 수 있다! 이 애매모호한 정의(라고 해도 누군가가 공들여 작성한 것이겠죠? 죄송합니다)를 실제 프로그래밍 언어의 특성을 활용하여 다음과 같이 재정의해볼 수 있을 것이다.

 

= 사전에 정의한 함수의 return 값에 도달할 때까지 자기 자신을 호출하는 함수. 

 

재귀함수의 가장 대표적인 예시로는 팩토리얼 { n! = n * (n-1) * (n-2) ... 3* 2 * 1 } 함수가 있다. n! 을 구하기 위해 for문이나 while 문을 활용하여 다음과 같은 코드를 구현할 수 있다. 

n = int(input())
result = 1

for i in range(1, n+1):
    result = result * i

print(result)

앞서 말한 바와 같이 for 문이나 while 문과 같은 반복문을 활용하여 코드를 구현할 수도 있겠으나... 재귀함수를 사용하면 코드 본문이 간결해지는 것을 확인할 수 있다! 해당 함수를 정의한 후, 코드 본문에서 해당 함수를 한 번만 실행시키면 되기 때문이다! 같은 맥락으로 사용하는 변수의 수도 줄어들기 때문에 코드가 간결해진다. 하지만 재귀함수에도 단점이 있는데... 그것은 바로 메모리 사용량이 늘어난다는 것이다! 메모리 사용량은 자연스레 코드 수행 시간에도 영향을 미치게 된다.

# 백준 10872 팩토리얼 Python3

import sys

def factorial(N):
    if N == 1 or N==0:
        return 1

    return N * factorial(N-1)

N = int(sys.stdin.readline().strip())
print(factorial(N))

백준 10872 팩토리얼 Python3

팩토리얼 재귀함수 도식화

위 사진은 factorial 함수가 어떻게 결과 값을 return 하는지를 도식화한 그림이다. 먼저 5!를 구하기 위해 factorial(5)를 호출한다. 이후 factorial(5)는 5*factorial(4)를 호출하게 되고, 다시 factorial(4)가 실행되면서 4*factorial(3)을 return 한다. 이렇게 return 값에서 자기 자신(함수)를 호출하게 되고, 최종적으로 해당 함수의 종료조건인 N==1 or N==0 에 다다르면 1을 return 하며 함수 호출을 멈추게 된다. 이 과정에서 종료조건 if N == 1 or N==0: return 1 이 중요한데, 해당 조건문이 없게 되면 지속해서 재귀함수를 호출하게 될 것이다. 따라서 Python의 경우 RecursionError: maximum recursion depth exceeded 에러 메시지를 호출하게 된다. 즉, 재귀함수를 작성할 때에는 입력하는 모든 값에 대해 재귀함수를 호출할 때 종료조건에 도달할 수 있는가를 살펴보아야 할 것이다.

 

* Python의 경우 최대 재귀 함수 호출에 대한 제한 (1000번)을 두고 있다. 1000번 보다 더 많이 함수를 호출해야 하는 경우가 생긴다면 아래의 코드를 이용하여 제한을 풀 수 있다.

import sys
limit = 2000
sys.setrecursionlimit(limit)

 

아래의 문제들은 백준 단계별 풀어보기에 있는 재귀함수란의 문제들을 파이썬 코드로 구현한 것이다.

#백준 10870 피보나치 수 Python3

import sys

def Fibo(n):
    if n == 0 or n==1:
        return n

    return Fibo(n-1) + Fibo(n-2)

n = int(sys.stdin.readline().strip())
print(Fibo(n))

백준 10870 피보나치 수 Python3

 

#백준 17478 재귀함수가 뭔가요? Python3

import sys

def recursive(N1, N2):

    print('_' * (N2-N1) * 4 + "\"재귀함수가 뭔가요?\"")

    if N1 == 0:
        print('_' * (N2-N1) * 4 + "\"재귀함수는 자기 자신을 호출하는 함수라네\"")

    else:
        print('_' * (N2-N1) * 4 + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.")
        print('_' * (N2-N1) * 4 + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
        print('_' * (N2-N1) * 4 + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"")
        recursive(N1-1, N2)
             
    print('_' * (N2-N1) * 4 + "라고 답변하였지.")
    
N = int(sys.stdin.readline().strip())

print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
recursive(N, N)

백준 17478 재귀함수가 뭔가요? Python3

 

#백준 11729 하노이 탑 이동 순서 Python3

import sys

def hanoi(start, through, finish, N):
    if N == 1:
        print(start, finish)

    else:
        hanoi(start, finish, through, N-1)
        print(start, finish)
        hanoi(through, start, finish, N-1)
    
N = int(sys.stdin.readline().strip())

print(2**N -1)
hanoi(1,2,3,N)

백준 11729 하노이 탑 이동 순서 Python3

 

11729번 같은 경우에는 설명이 필요할 것 같아 다음과 같은 그림을 그려보았다.

1번 그림: n개의 원판을 1번에서 3번 기둥으로 옮긴다는 것은

2번 그림: n-1개의 원판을 2번 기둥(최종적으로 n개의 원판이 3번에 옮겨져야 하기 때문에 n-1개의 원판은 2번 기둥으로 가야 함)으로 옮기고

3번 그림: n번째 기둥을 3번 기둥(최종 목적지)에 옮긴 후

4번 그림: 다시 2번 기둥에 있던 n-1개의 원판을 1번 기둥(경유지)를 거쳐 3번 기둥(최종 목적지)으로 옮기는 과정을 모두 포함한다.

hanoi(start, finish, through, N-1) #a
print(start, finish) #b
hanoi(through, start, finish, N-1) #c

따라서 else 구문에서 다음과 같은 실행문을 구현하였다. 처음 입력으로 들어온 start, through, finish는 #a 에서 각각 start, finish, through 가 되어 2번 그림을 수행하고, #b를 통해 3번 그림을, 마지막으로 처음 입력으로 들어온 start, through, finish는 #a 에서 각각 through, start, finish 가 되어 3번 그림을 수행한다. 이 과정에서 재귀함수 종료 조건이 있어야 하는데, 이는 옮겨야 하는 원판이 1개일 때 움직이는 횟수가 한 번임을 고려하여 작성해주면 된다. 그리고 하노이 탑을 이동시키기 위한 총 이동 횟수는 함수 내부에서 카운트 해줘도 되지만, 일반항을 구했을 때 2**n -1 임을 알 수 있기에 다음과 같이 작성하였다.

 

#백준 2447 별찍기 Python3

def stars(n, base, check):
    star_list = []

    if n == 3:
        return base

    else:

        for i in base:
            star_list.append(i * 3)

        for i in base:
            star_list.append(i + ' ' *(check//n) + i)

        for i in base:
            star_list.append(i * 3)

        return stars(n//3, star_list, check)

base = ['***', '* *', '***']
n = int(input())
result = stars(n, base, 3*n)

for star in result:
    print (star)

백준 2447 별찍기 Python3

 

느낀 점

재귀함수... 쉬운 문제는 쉽고 어려운 문제는 죽도록 어렵다! 특히 별찍기는 푸는데 애를 먹어서 다른 코드들을 참고하였는데, 다음에 해당 글을 수정하면서 다시 이해해보고 설명도 덧붙여야겠다... 아마 자료구조 강의를 들으며 heap을 구현하기 위해 C로 재귀함수를 사용한 적이 있던 것 같다. reheap_down reheap_up 이었던 것 같은데,,, 그때는 return 값으로 주어지는 것들이 현재 자료의 구조에 영향을 미쳤기 때문에 많이 고생했던 것 같은데, 이 문제들은 그것과는 다르게 덜 복잡했던 것 같기도 하다... 그래도 어려운 건 마찬가지인듯... 오늘따라 느낀 점에 쩜 내지 . 내지 마침표 내지 full stop이 많은 것 같다! 다음 느낀 점에는 마침표가 많이 없길 바라며 ~.~