[알고리즘] 재귀(Recursion)
* 스스로 공부한 내용을 바탕으로 작성한 글입니다. 부정확한 부분이나 오류가 있을 수 있으며, 발견 시 댓글로 알려주세요!
알고리즘 카테고리에서 첫 번째로 다룰 것은 '재귀'이다. 재귀라는 것 자체는 알고리즘보다는 문법의 한 형태에 가깝다고 생각하지만, 앞으로 다룰 다양한 알고리즘들을 구현하기 위해 자주 활용되는 코드 작성 방식 중 한 가지이다. 그렇기 때문에 가장 먼저 다룰 주제로 선정해 보았다. 재귀가 무엇인지 살펴보겠다.
재귀란?
재귀란 함수 안에서 함수 자기 자신을 호출하는 것을 말한다. 때로는 순환이라고도 말하기도 한다. 재귀는 함수내부에서 자기 자신을 계속 호출하는 특징이 있기 때문에, 반드시 종료 조건을 만들어 주어야 한다. 그렇지 않으면 함수가 끝나지 않고 계속 반복되기 때문이다. 이런 상황을 방지하기 위해 파이썬은 최대 재귀 한도(Maximum recursion depth)를 미리 정해두어, 허용되는 재귀 호출의 최대 반복 횟수가 제한되어 있다. 최대 재귀 한도는 파이썬 버전과 운영체제 등에 따라 차이가 존재하며, 재귀 한도를 직접 설정해 줄 수도 있다. 파이썬에서 재귀 한도를 지정해 주기 위해서는 sys 라이브러리를 사용하면 된다.
# 파이썬의 최대 재귀 한도 지정
import sys
sys.setrecursionlimit(지정할재귀한도)
예시 0 ) 타이머 구현
재귀는 다양한 방식으로 활용할 수 있다. 가장 간단한 예시로, 초를 셀 수 있는 타이머를 구현해 보았다. 시작하고자 하는 초를 입력해 주면, 해당 초부터 0까지 줄어드는 초를 하나씩 출력하고 0이 되면 'Time Over!'라는 메시지를 띄도록 하였다.
def timer(num):
if num == 0:
print("Time Over!")
else:
print(num)
timer(num-1)
해당 코드를 통해 timer(5)를 실행해보면 다음과 같은 결과가 나온다. 5부터 1까지는 if문의 조건에 해당되지 않기에 해당 숫자를 출력하고, 하나 줄어든 숫자를 전달하며 재귀가 진행된다. 숫자가 최종적으로 0이 되었을 때는 if문이 시행되며 동작이 종료되게 된다.
예시 1 ) 팩토리얼 함수 구현
재귀의 가장 대표적인 예시 두 가지를 추가로 구현해 보겠다. 첫 번째는 팩토리얼 함수 구현이다. 팩토리얼 계산은 n! = n*(n-1)*(n-2)*…*2*1로 1부터 n까지를 모두 곱하는 연산이다. 이 계산을 일반적으로는 for문을 활용하여 구할 수도 있지만, 재귀 함수로도 구현하게 되면 훨씬 더 간편하게 구현할 수 있다. 재귀함수를 사용했을 때의 동작 원리는 다음과 같다. 숫자가 n에서 1까지 줄어들며 재귀 함수를 계속 호출하며 내려가다가, factorial(1) = 1임을 반환하고, 그다음부터는 factorial(2) = 2 * factorial(1) → factorial(3) = 3 * factorial(2) → ... → factorial(n) = n * factorial(n-1)의 과정을 통해 최종적으로 n!을 구할 수 있게 된다.
팩토리얼을 파이썬 코드로 구현하면 다음과 같다.
num = int(input())
# for문으로 팩토리얼 구현
result = 1
for x in range(1,num+1):
result *= x
print(result)
# 재귀로 팩토리얼 구현
def factorial(n):
if n <= 1:
return 1
return n * factorial(n-1)
print(factorial(num))
예시 2 ) 피보나치수열 구현
재귀의 두 번째 예시는 피보나치수열 구현이다. 피보나치 수열이란 첫항과 둘째항은 1이고 그 이후의 항들은 바로 앞의 두항의 합인 수열이다. 아래의 표를 보면 무슨 말인지 더 이해가 잘 될 것이다. 피보나치수열의 세 번째 항은 첫 번째 항인 1과 두 번째 항인 1을 더한 2를 갖고, 여섯 번째 항은 네 번째 항인 3과 다섯 번째 항인 5의 합인 8을 갖는다. 피보나치수열은 재귀를 사용하면 효율적으로 구현할 수 있다.
피보나치수열을 파이썬 코드로 구현하면 다음과 같다.
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n-1) + fib(n-2)
재귀는 백트래킹이나 DFS와 같은 알고리즘에서도 굉장히 많이 활용되고, 이 내용을 정확하게 이해하고 있으면 코드를 단순화하는데 많은 기여를 할 수 있기에 개념을 확실히 잡아두고 가면 좋다!