개요
재귀 함수는 처음에 코딩 공부를 할 때 벽과 같은 존재였다. 디버깅이 약했던 과거의 나는 내가 짠 몇 줄 안되는 코드에서 도대체 무슨 일이 일어나는지 알 수가 없었다.
재귀 함수와 나는 개인적인 인연이 있다. 대학교 입학 준비 당시 면접에서 면접관님이 나한테 “재귀 함수가 뭐냐?” 라고 물었던 것이 5년이 지난 아직까지 기억이 생생하게 난다. 그때의 나는 … “함수가 실행되었을 때 자기 자신을 도출하는 함수입니다.” 라고 답변했고. 면접관님이 도출이란 표현을 호출로 정정해야 한다고 코멘트를 주셨는데 그때 당시 부끄러운 기억이 아직까지난다.
백트래킹 및 CS를 공부한 지금은 재귀 함수가 뭔 놈인지 이제서야 알게 되었다. 내가 지금 알고 있는 재귀 함수에 관한 내용을 소개하려고 한다.
(엘리베이터에서의 재귀 함수)재귀 함수란 무엇인가 ?
재귀 함수의 정의
재귀 함수(recursive)는 함수 안에서 자기 자신을 호출하는 함수이다.
자기 자신을 계속해서 호출하기 때문에 재귀의 기저 조건(탈출 조건)이 없다면 탈출할 수 없다. 반드시 재귀 함수를 정의할 때는 기저 조건을 완벽하게 세워야 한다. 만약 재귀 함수가 무한 루프를 돈다면 기저 조건을 올바르게 세우지 못한 것이다.
재귀 함수의 예
def fibo(n):
if n == 1:
return 1
if n== 2:
return 1
return fibo(n-1) + fibo(n-2)
print(fibo(5))
print(fibo(10))피보나치수열은 재귀 함수의 대표적인 예시이다. 피보나치수열은 n 번째 수는 n-1 번째 수와 n-2 번째 수의 합임을 정의로 가지는 수열이다. 피보나치수열의 첫 번째 수와 두 번째 수는 1이므로 기저 조건으로 설정해주고 피보나치수열의 정의를 그대로 리턴문에 옮겨주면 구현이 끝이난다.
재귀 함수의 장점
재귀 함수는 특정한 문제 및 자료구조(트리)에서 굉장히 쉽게 코드를 짤 수 있도록 도와준다. 아무래도 함수의 재사용성을 굉장히 높여 문제를 풀기 때문에 코드가 간결할 수 밖에 없다. 또한 하노이의 탑, 순열, 피보나치와 같은 문제 자체가 재귀적인 문제들을 해결할 때도 매우 쉽게 코드를 구현할 수 있다. 즉, 짧지만 매우 강력한 코드를 완성할 수 있다.
또한 재귀 함수로 문제를 해결한다는 것은 반복적인 코드로 전체 문제를 해결한다는 것이다. 그 말은 문제를 작은 문제로 분해하여 큰 문제를 해결한다는 것으로 생각할 수 있다. 큰 문제를 작은 문제로 나누었기 때문에 코드 가독과 문제 풀이가 쉬워질 수 있다.
재귀 함수의 단점
아이러니하게도 위의 장점이 단점이 될 수도 있다. 재귀 함수가 익숙하지 않은 초보 프로그래머 입장에서 재사용성을 높여 코드가 간결하기 때문에 디버깅 시 재귀 함수의 깊이에 따른 스택 값(변수 값)을 추적하기 어려울 수 밖에 없다. 또한 알맞은 기저 조건을 세우기 역시 힘들 것이다.
시간, 메모리 자원의 입장에서도 손해이다. 함수를 사용했을 때 드는 비용을 생각해 보자. 함수의 비용으로는 대표적으로 컨텍스트 스위칭이 있을 것이다.
컨텍스트 스위칭은 다음 작업을 하기 위해 현재의 작업을 중지하고 작업 내용을 저장해놨다가 다음 작업이 끝났을 때 저장해놓았던 현재의 작업 내용을 다시 불러오는 것을 의미한다.
재귀 함수에서의 컨텍스트 스위칭 비용은 일반 함수의 비용보다 훨씬 크다고 말할 수 있다. 함수는 함수의 내용물을 완전히 실행하고 return시 할당받은 메모리를 반환한다. 재귀 함수는 함수가 다 끝나기 전에 새로 함수를 다시 시작하므로 기저 조건을 만족할 때 까지 메모리를 계속 차지하게 된다.
재귀 함수의 비용을 줄이는 방법
꼬리 재귀
코드의 가독과 간결함의 장점과 스택 메모리와 시간을 많이 소모하는 단점을 가진 재귀함수의 단점을 극복할 수 있는 방법이 있다. 바로 ‘꼬리 재귀’(tail recursion)로 불리는 재귀 함수의 최적화 방법이다.
꼬리 재귀의 원리는 알고 보면 간단하다. 컨텍스트 스위칭을 해야 하는 이유가 무엇인가 🤔? 새로운 함수를 호출하고 내가 다음 작업들을 이어서 해야 하기 때문에 이전 작업 정보를 저장하는 것이다. 그러면 다음 작업이 없다면 컨텍스트 스위칭을 안 해도 되는 것으로 생각할 수 있다. 말이 쉽지 꼬리 재귀로 코드 짜는 것은 쉽지 않은 것 같다.
def fibo(n, cur=0, next=1):
if n == 0:
return cur
return fibo(n-1, next, cur+next)
print(fibo(5))
print(fibo(10))피보나치수열을 꼬리 재귀로 나타낸 코드이다. 꼬리 재귀에서 가장 중요한 점은 반드시 return 부분에 재귀문을 실행해야 하며 ‘+’와 같은 다른 연산은 없어야 한다. 다른 연산을 실행한다면 위에 말했던 아직 끝내지 못한 작업을 끝내기 위해 컨텍스트 스위칭을 시도할 것이다 😢😢😢
꼬리 재귀가 불가능한 경우
꼬리 재귀는 언어에 따라 사용하지 못할 수 있다. 꼬리 재귀는 코드를 어떻게 짜도 결국 컴파일러에 의존하게 된다. 슬프게도 언어에 따라 컴파일러가 다르므로 언어마다 꼬리 재귀의 지원 여부가 다르다. 사실 위의 피보나치수열을 꼬리 재귀로 만든 코드도 꼬리 재귀의 형태를 가지고 있지만 꼬리 재귀를 실행하지는 않는다😟… Python, JAVA 및 많은 프로그래밍 언어들 꼬리 재귀를 지원하지 않는다.
결론
재귀 함수는 컨텍스트 스위칭 때문에 엄청난 비용이 든다. 이를 줄이기 위한 꼬리 재귀라는 최적화 방법이 있지만 언어마다 꼬리 재귀를 지원해 주지 않을 수 있다. 재귀 함수를 사용한 알고리즘 문제 풀이시 시간 초과가 난다면 정답이 될 수 있는 부분만 탐색하도록 가지 치기를 생각해 보자.
