이번 시간에는 함수 안에 함수, 그 안에 함수... 입문자들이 많이 어려워하는 그 개념! 그러나 개발자라면 반드시 알아야 하는 바로 그 개념! 재귀 함수에 대해 함께 알아보겠습니다.
💫 재귀 함수 개요
개념 설명에 앞서 재귀 함수는 많은 사람들이 어려워한다는 것을 알아두었으면 좋겠네요. 그렇지만 조금만 참고 연습하면 익숙해질 수 있기 때문에 힘들더라도 포기하지 맙시다.
영화 인셉션을 본 적이 있나요? 인셉션에서는 꿈을 꾸면 그 속에서 또 꿈을 꾸고 또 그 속에서 꿈을 꿉니다. 꿈이 여러번 중첩되는 거죠.
이와 유사하게 재귀 함수(recursive function)는 자기 자신을 호출하는 함수입니다. 간단한 예시를 함께 봅시다.
def countdown(n):
if n > 0:
print(n)
countdown(n-1)
countdown(5)5
4
3
2
1countdown 함수는 정수 n부터 1까지 출력합니다. 파라미터로 5를 넘겨주었더니 5에서 1까지 차례로 출력되었습니다. 그런데 코드를 보면 반복문이 없음에도 계속해서 숫자를 출력해줍니다. 어떻게 된 걸까요? 한 줄씩 함께 봅시다.
countdown(5)if 5 > 0:
print(5)
countdown(5-1)countdown 함수를 호출하면 파라미터 5가 if문에 들어갑니다. 5는 0보다 크기 때문에 콘솔에 5를 출력하고 다음 줄에서 countdown(4)를 호출합니다.
그럼 이번에는 파라미터 4가 if문 안에 들어가겠죠? 이런 식으로 파라미터가 0이 될 때까지 함수 속에서 함수가 계속 호출됩니다. 파라미터가 0이 되면 if문의 조건을 충족시키지 않으므로 그대로 함수를 종료합니다.
countdown(0)이 끝나면 차례로 그 함수를 포함하고 있던 상위 countdown 함수들이 종료됩니다. countdown(5)까지 종료되면 프로그램이 끝납니다.
💫 재귀 활용 예시
이번에는 팩토리얼(Factorial)을 계산하는 함수의 예시를 봅시다.
n! = 1 * 2 * 3 * ... * (n-2) * (n-1) * nn팩토리얼은 자연수 1부터 자연수 n까지의 곱입니다. 보시는 바와 같이 팩토리얼은 느낌표(!)로 나타냅니다. 예를 들어, 3팩토리얼은 '3!'과 같고 '1 2 3'의 연산을 하여 '6'의 값을 가집니다.
0! = 1
1! = 1
2! = 1 * 2
3! = 1 * 2 * 3
4! = 1 * 2 * 3 * 4
5! = 1 * 2 * 3 * 4 * 5예외적으로 0 팩토리얼은 1이 됩니다. 1 팩토리얼은 당연히 1이겠죠?
이제 함수를 작성해봅시다. 사실 반복문을 사용해도 되지만 이번 시간은 재귀 함수를 배우는 시간인만큼 재귀 함수로 작성해보도록 합시다.
일단 재귀적으로 문제를 푼다는 것에 대한 논리를 이해해 봅시다. 재귀 함수 문제의 논리는 같은 형태의 더 작은 문제를 풀고 이를 이용해서 기존 문제를 푸는 것입니다. 여기서 더 작은 문제를 부분 문제(Subproblem)라고 부릅니다.
다시 말해, 재귀 함수의 문제 풀이는 부분 문제를 먼저 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것이죠. 그럼 팩토리얼의 부분 문제는 뭘까요?
4 팩토리얼에서 마지막 4를 제외한 나머지 수들의 곱은 3 팩토리얼과 같습니다. 3 팩토리얼은 4 팩토리얼과 같은 형태면서 더 작은 문제죠? 그러니까 3 팩토리얼은 4 팩토리얼의 부분 문제가 됩니다.
이런 식으로 내려오다 보면 결국 0 팩토리얼까지 내려오게 되는데 앞서 보았듯 0 팩토리얼은 예외적으로 1이라는 수를 가집니다. 따라서, 0을 기점으로 조건을 나눠볼 수 있겠네요.
n = 0인 경우, n! = 1 # base case
n > 0인 경우, n! = (n-1)! * n # recursive case
재귀 함수 문제를 풀 때는 항상 이런 식으로 경우를 나누게 됩니다. 위 경우를 base case라고 부르고 아래 경우를 recursive case라고 부릅니다.
base case는 문제가 충분히 작아서 바로 풀 수 있는 경우를 말합니다. 우리는 0 팩토리얼이 1이라는 걸 미리 알고 시작하기 때문에 n이 0인 경우에는 따로 풀어야할 부분 문제가 없습니다.
반면, recursive case는 재귀적으로 부분 문제를 푸는 경우를 말합니다. 예를 들어, n이 4면 4 팩토리얼을 알아내기 위해 3 팩토리얼이라는 부분 문제를 풀어야 합니다.
만약 base case 없이 recursive case만 있다면 재귀적으로 계속 함수를 호출하여 프로그램이 절대 끝나지 않습니다. 따라서, 재귀 함수를 정의할 때는 항상 base case와 recursive case를 모두 생각해내야 합니다.
이제 코드로 한 번 바꿔 봅시다.
def factorial(n):
if n == 0:
return 1
return factorial(n-1) * n위 코드의 원리는 간단합니다. n이 0이면 1을 리턴하면 되고 0이 아니면 부분 문제(4 팩토리얼의 경우, 3 팩토리얼)와 현재 수를 곱한 값을 리턴해주면 됩니다.
print(factorial(3))3 팩토리얼 함수의 결과가 도출되는 과정을 추적해봅시다. 파라미터에 3이 들어가면 3은 0과 다르므로 'factorial(3-1) * 3'이 됩니다. 이제 3 팩토리얼 함수 속 2 팩토리얼이 호출 되고 같은 과정을 반복한 후, n이 0이 되면 1을 리턴한 뒤 0 팩토리얼 함수를 종료합니다.
리턴된 1은 팩토리얼 0을 대체하여 팩토리얼 1에서 '1 곱하기 1'을 리턴합니다. 또, 팩토리얼 1의 리턴 값 1이 팩토리얼 1을 대체하여 팩토리얼 2에서 '1 곱하기 2'을 리턴합니다. 이제 팩토리얼 2를 대체한 값 2가 팩토리얼 3에서 '2 곱하기 3'을 하여 6을 리턴합니다. 이 리턴 값은 print 함수에 의해 출력됩니다.
💫 재귀 함수 vs. 반복문
통상 반복문으로 풀 수 있는 문제는 재귀 함수로도 풀 수 있습니다. 반대로 재귀 함수로 풀 수 있는 문제도 반복문으로 풀 수 있죠. 앞서 보았던 factorial 함수의 코드를 반복문으로도 봅시다.
def factorial(n):
result = 1
for i in range(1, n+1):
result = result * 1
return result사실 재귀 함수에는 치명적인 단점이 있습니다. 이를 설명하기 전에 우선 함수의 내부적인 동작 방식을 알려 드리겠습니다.
함수를 호출하면 프로그램이 함수 부분으로 넘어가죠? 이때, 함수가 끝나면 어디로 돌아가야 할 지 알아야 하므로 컴퓨터는 위치를 내부적으로 기록해 둡니다. 이로 인해 함수가 끝나면 원래 위치로 돌아갈 수 있는 것이죠. 그리고 위치에 대한 기록은 지워집니다.
이렇게 위치를 기억해두는 장소를 'call stack'이라고 합니다. 그런데 재귀 함수를 너무 많이 호출하게 되면 call stack이 계속해서 쌓이면서 더 이상 기록할 공간이 없어지고 결국 과부하로 인해 프로그램이 중단됩니다.
개발자 커뮤니티 stackoverflow를 아시죠? 이 stackoverflow의 어원이 바로 call stack 과부하로 인한 에러인 'StackOverflowError'에서 온 것입니다.🤣🤣🤣
Python은 심각한 에러를 방지하기 위해 call stack을 1000개까지만 허가해줍니다. 그래서 만약 factorial(2000) 같이 너무 큰 파라미터를 넘겨 주면 'RecursionError'가 뜨고 프로그램이 중단됩니다.
그렇다면 재귀 함수는 언제 쓰면 좋을까요? 코드 중에는 반복문으로 구현하면 지저분하지만 재귀 함수로 구현하면 깔끔한 경우가 있습니다. 그럴 때, 재귀 함수를 쓰는 것이죠.
하지만 그 반대의 경우도 있다는 점을 알아야 합니다. 만약 재귀적으로 너무 많은 호출이 있는 알고리즘이면 반복문을 사용해 주는 것이 더 효율적일 것입니다. call stack으로 인한 오류도 방지할 수 있구요.
이번 시간에는 재귀 함수의 정의와 그 예시들을 살펴 봤습니다. 많이 어려우셨나요? 함수 속 함수라는 컨셉과 기존 문제를 풀기 위해 선행해서 풀어야할 부분 문제로 나누어 생각해 보시면 좀 더 이해가 되리라 생각합니다.
다음 시간에는 재귀 함수를 연습해보기 위해 몇 가지 문제를 같이 풀어봅시다.
마지막으로 재귀 함수가 어려우신 분들을 위해 좋은 글 하나를 첨부해드립니다. 재귀 함수는 여러 사람으로부터 어렵다고 소문난 개념입니다. 그러니 어렵더라도 포기하지 마시고 천천히 이해해도 된다는 생각으로 꾸준히 연습해주세요.
익숙해지면 좋은 코드를 쓸 수 있는 또 하나의 팁이 될 수 있으니 말입니다.
* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.