[알고리즘 일반] 재귀 함수

도깨비젤리

2021. 6. 9. 22:32

들어가는 말

알고리즘 공부를 하다보면 어느 순간 턱 막히는 지점이 있습니다. 분명 배우긴 배웠는데도 뭔 소리인지도 모르겠고, 공부할 때는 알겠는데 막상 구현해보라면 손이 안 움직이는 크고 작은 고비들이 알고리즘의 세계에는 존재합니다.

그 많은 고비 중에서 재귀 함수가 가장 먼저 등장합니다. 저도 재귀함수를 공부할 적에는 정말 이해가 안되서 혼자서 벽도 쳐보고, 소리도 질러보고 오만 생쑈를 다했습니다. "그렇게 복잡한 개념이라면, 아예 다음으로 미루면 되지 않느냐?" 라고 생각하실 수 있겠습니다.

맞습니다. 사실 재귀적 구현으로 풀 수 있는 문제들은 다른 방법으로도 충분히 풀 수 있습니다. 그럼에도 불구하고 우리가 재귀 함수를 배워야하는 이유는, 프로그래밍 세계에서 통하는 하나의 황금률 때문입니다.

" 모든 문제에 들어맞는 만능열쇠는 없다"

재귀 함수를 모르고 넘어가도 당장에는 큰 문제가 없을지는 몰라도, 알고리즘의 바다에 깊게 발을 내딛을 수록 발 밑이 푹 꺼지는 느낌이 드실껍니다. 재귀 함수의 이해가 당장은 어려울 지라도, 조금만 참고 내재화 하시길 바랍니다.

재귀함수란??

재귀함수의 사전적 의미는 정의 단계에서 자신을 재참조하는 함수입니다. 사전에 적힌 말이 늘 그렇듯 폼 나게 설명하긴 하는데 짧게 말씀드리면, 재귀함수 == 인셉션 이라고 생각하시길 바랍니다.

영화 인셉션에서 주인공 일행은 "드림머신" 이라는 기계를 이용해 꿈에서 더 깊은 꿈으로 이동한다

주인공 도미닉 코브가 "드림머신"이라는 기계로 꿈에서 더 깊은 꿈으로 이동하는 것 처럼, 우리들도 "재귀함수"를 이용해서 함수에서 더 깊은 함수로 이동할 수 있습니다. 간단한 예시 코드를 보시겠습니다.

def recursion(level):
    if level == 5:
    	print('recursion을 종료합니다')
        return
    
    print(f'현재 level은 {level}입니다.')
    print(f'level {level+1}로 이동합니다.\n')
    recursion(level+1)



recursion(0)

위 recursion이라는 함수는 level이라는 값을 parameter로 받아 실행됩니다.

처음 등장하는 if문을 보면 level == 5일때 return이 되어 종료가 됩니다.

오잉? 그런데 실행부에서는 recursion(0)으로 호출했습니다. 뭐지요? 그럼 recursion 함수는 종료 되지 않는 걸까요???

하지만 놀랍게도 결과는 아래와 같습니다.

현재 level은 0입니다.
level 1로 이동합니다.

현재 level은 1입니다.
level 2로 이동합니다.

현재 level은 2입니다.
level 3로 이동합니다.

현재 level은 3입니다.
level 4로 이동합니다.

현재 level은 4입니다.
level 5로 이동합니다.

recursion을 종료합니다.

이런 신통방통한 일이 일어나는 이유는, print 문 이후에 나오는 recursion(level+1)에 있습니다. recurison 스스로가 recursion 을 호출하는데, 호출할적에 parameter인 level을 +1 해서 넘겨주기 때문이지요.

그런데, 매 반복마다 인자가 변하는 구조....어디서 많이 보지 않으셨나요???

맞습니다. 재귀함수는 반복문과 유사한 구조를 가지고 있습니다.

재귀함수와 반복문의 차이??

좋던 싫던 간에, 프로그램은 항상 반복되는 작업을 수행하게 되어있습니다. 그리고 그 반복을 구현하는 대표적인 로직이 for문과 while문입니다. 재귀함수도 for / while문과 동일하게 반복되는 로직을 구현하기 위해 사용되는 개념입니다. 그렇기 때문에, 반복문으로 구현할 수 있는 코드는 재귀 함수로도 구현 할 수 있고, 재귀함수로 구현할 수 있는 코드는 반복문으로도 구현 할 수 있습니다.

그러면 위 코드를 반복문으로 바꿔보겠습니다.

for i in range(5):
    print(f'현재 level은 {i}입니다.')
    print(f'level {i+1}로 이동합니다.\n')
    if i == 4:
        print('loop를 종료합니다')

결과

현재 level은 0입니다.
level 1로 이동합니다.

현재 level은 1입니다.
level 2로 이동합니다.

현재 level은 2입니다.
level 3로 이동합니다.

현재 level은 3입니다.
level 4로 이동합니다.

현재 level은 4입니다.
level 5로 이동합니다.

loop를 종료합니다

보시다시피 결과는 동일합니다. 하지만, 재귀적 구현은 반복되는 기능에 이름을 붙여서 관리할 수 있다는 장점과, 무분별한 변수 사용을 막아줍니다. 같은 동작을 다시 한번 수행해야할 때 처음부터 끝까지 다시 타이핑 해야하는 반복문과 다르게, 재귀함수는 호출만 해주면 되는 것은 덤이고요.

간단한 예시를 들어서 크게 체감이 안될 수 도 있겠지만, 구현이 복잡해질 수록 재귀함수가 반복문보다 더 간단히 표현되는 경우가 많습니다.

재귀함수의 단점

복잡한 식일 수록 재귀적 구현이 편리하다면, 왜 모든 반복문을 다 재귀함수로 바꾸지 않을까요??

앞서 말했듯, 모든 문제에 들어맞는 만능열쇠는 없습니다. 빛이 있으면 어둠이 있듯, 재귀적 구현에도 명확한 단점이 있습니다.

재귀 함수가 깊어진다면 (반복이 많아질 수록) 프로그램이 비정상적으로 종료 될 수 있다.
반복문보다 느린 속도

재귀함수는 기본적으로 스택 메모리를 사용합니다. 스택 메모리란 쉽게 말해서 여러분들의 책상과 같은 역할을 합니다. 컴퓨터는 어떤 작업을 할 때, 스택 메모리라는 책상 위에서 작업을 하는 거죠. 여러분들이 컴퓨터한테 1000 조각 직쏘 퍼즐을 맞춰보라고 시켰다고 가정해봅시다.

반복문으로 구현한 직쏘 퍼즐은, 1000조각 짜리 퍼즐을 한번에 컴퓨터에게 주게됩니다. 책상 공간이 모자라긴 하지만,

컴퓨터는 어떻게든 공간을 잘 활용해서 퍼즐을 맞추는데 성공합니다.

반면, 재귀함수로 구현한 직쏘퍼즐은 10조각 짜리 퍼즐을 컴퓨터에게 줍니다. 컴퓨터가 10조각 짜리 퍼즐을 다 맞춰갈 때쯤, 재귀함수가 갑자기 컴퓨터를 멈춰세우더니, 이렇게 말합니다.

"이야~~ 벌써 다 맞춰가네?? 야 근데, 미안한데 그거 말고 이것부터 해줘라."

그러면서 새로운 10조각 짜리 퍼즐을 줍니다. 컴퓨터는 어이가 없지만, 맞추던 퍼즐을 책상 위에 조심스럽게 내려놓고, 새로 받은 퍼즐을 맞추기 시작합니다.

그렇게 2번째 퍼즐을 다 맞춰갈 때쯤, 재귀함수가 갑자기 컴퓨터를 멈춰세우더니, 이렇게 말합니다.

"이야~~ 벌써 다 맞춰가네?? 야 근데, 미안한데 그거 말고 이것부터 해줘라."

그렇게 3번째 퍼즐을 다 맞춰갈 때쯤, 재귀함수가 갑자기 컴퓨터를 멈춰세우더니, 이렇게 말합니다.

"이야~~ 벌써 다 맞춰가네?? 야 근데, 미안한데 그거 말고 이것부터 해줘라."

그렇게 4번째 퍼즐을 다 맞춰갈 때 쯤........(생략)

그런식으로 42번째 퍼즐을 받았을 때, 컴퓨터의 책상은 앞서 내려놓았던 퍼즐로 꽉 차게 되어, 더 이상 아무것도 할 수 없게 되어 컴퓨터가 GG를 칩니다.

예시가 좀 유치하긴 했는데, 요지는 재귀가 너무 깊어지면 컴퓨터의 작업을 망칠 수 있을 뿐만 아니라, 중간중간 말을 걸기 때문에, 실행속도도 반복문에 비해 느립니다.

(또한, 파이썬은 재귀가 너무 깊어진다 싶으면 알아서 에러를 뿜습니다.)

재귀함수로 구현할 때 주의해야할 점

반복문을 작성할 때 종료 시점을 지정해주지 않으면 무한 루프가 발생하는 것처럼, 재귀함수도 return 시점을 정해주지 않으면 무한히 재귀가 발생합니다. 보통은 재귀함수의 parameter가 특정 숫자가 되면 return 하게 하는 것으로 breakpoint를 정합니다. 재귀함수를 연습할때 자주하는 실수인만큼 주의하시길 바랍니다.

마치며

재귀함수는 메모리를 많이 차지하고 성능이 반복문에 비해 느리지만, 코드를 더 직관적으로 짤 수 있고 반복해서 사용하기가 용이하다는 장점이 있습니다. 무조건 재귀함수 사용! / 무조건 반복문 사용! 이라고 이분법적으로 생각하지만 말고, 상황에 따라 적절하게 사용할 수 있도록 합시다.

연습하기 좋은 문제들 :

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

10829번: 이진수 변환

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000)

www.acmicpc.net

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

16505번: 별

출력 예제를 보고 별 찍는 규칙을 유추하여 별을 찍어 보자.

유령이 나오는 젤리하우스

[알고리즘 일반] 재귀 함수

티스토리툴바