재귀함수는 자기 자신을 호출하는 함수로, 반드시 종료 조건이 필요합니다. 팩토리얼, 문자열 뒤집기 등에 활용되며, Python은 기본 1000회 재귀 제한이 있습니다.

1. 재귀함수(recursion)

재귀함수는 함수 내부에서 자신을 다시 호출하여 작동하는 함수입니다. 아래 그림을 보면 예로 들 수 있습니다.

이러한 방법으로 재귀함수는 반복적인 작업을 수행할 수 있습니다. 하지만 무한 반복을 피하기 위해 종료 조건이 필요합니다.

아래 코드는 실행시키지 마세요. 무한 반복됩니다.

# 주의! 실행하지 마세요!
def 숫자출력():
    print(1)
    return 숫자출력()

# 출력
1
1
1
.
.
.
1
1
1

위 숫자출력이라는 함수는 return으로 숫자출력 함수를 지속해서 호출하고 있습니다. 이렇게 될 경우 멈추는 조건이 없기 때문에 무한 반복에 빠지게 됩니다. 이처럼 자기 자신을 호출하는 함수를 재귀 함수라고 합니다.

1.1 무한 반복에 종료 조건을 부여

종료 조건을 부여하여 재귀함수를 유한하게 만들 수 있습니다.

def 숫자출력(count):
    if count > 100:
        return
    print(count)
    return 숫자출력(count+1) #값을 1부터 반복횟수 까지의 값을 출력

숫자출력(1)

위 예시에서는 count 변수를 사용하여 함수 호출 횟수를 제한합니다. 처음에는 숫자출력(1)이지만 숫자출력(1)의 return 값은 숫자출력(2)가 됩니다. 이렇게 count가 100이 넘게 되면 count > 100 조건이 True가 되어 함수는 return으로 종료됩니다.

1.2 팩토리얼 함수

팩토리얼은 재귀함수로 간단하게 구현할 수 있는 좋은 예시입니다. 아래 함수는 n 팩토리얼을 계산합니다.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)
factorial(5) # 출력: 120

종료 조건을 n == 1이 아니라 n <= 1로 쓴 것에 주목해주세요. n == 1로 두면 factorial(0)을 호출했을 때 조건에 걸리지 않고 -1, -2로 계속 내려가 무한 재귀에 빠집니다. 종료 조건은 '정확히 그 값일 때'가 아니라 '그 값을 지났을 때'까지 받아주도록 넉넉하게 잡는 것이 안전합니다.

# step1                         # step2
factorial(5) = 5 * factorial(4) = 5 * 24 = 120
factorial(4) = 4 * factorial(3) = 4 * 6 = 24
factorial(3) = 3 * factorial(2) = 3 * 2 = 6
factorial(2) = 2 * factorial(1) = 2 * 1 = 2
factorial(1) = 1

n의 값이 5가 입력되면 1이 아니기 때문에 5 * factorial(4)로 값을 리턴해야 합니다. 다만 factorial(4)의 리턴값을 알 수 없으므로 factorial(4)를 호출합니다. 위와 같은 방식으로 factorial(1)까지 진행됩니다. factorial(1)의 값은 if문에 True가 되어 값이 1이 됩니다. 이렇게 결과값이 재귀가 아닌 상태가 되면 다시 역순으로 타고 올라가며 계산됩니다. 따라서 factorial(5)에 값을 대입하면 팩토리얼 값이 계산되어 120이 출력됩니다.

1.3 문자열 거꾸로 출력하기

재귀함수를 이용하여 문자열을 거꾸로 출력할 수 있습니다.

def 거꾸로(s):
    if len(s) <= 1:
        return s
    else:
        return 거꾸로(s[1:]) + s[0]
거꾸로('hello') # 출력: olleh

여기서도 마찬가지로 len(s) == 1이 아니라 len(s) <= 1을 썼습니다. 빈 문자열이 들어와도 무한 재귀에 빠지지 않고 그대로 돌려주기 위해서입니다.

# step1                                # step2
거꾸로('hello') = 거꾸로('ello') + 'h' = 'olle' + 'h'
거꾸로('ello')  = 거꾸로('llo') + 'e'  = 'oll' + 'e'
거꾸로('llo')   = 거꾸로('lo') + 'l'   = 'ol' + 'l'
거꾸로('lo')    = 거꾸로('o') + 'l'    = 'o' + 'l'
거꾸로('o')     = 'o'                  = 'o'

s의 값이 ‘hello’가 입력되면 이것에 길이가 1이 아니기 때문에 거꾸로('ello') + 'h'를 리턴해야 합니다. 거꾸로(’ello’)의 리턴값을 알 수 없으므로 거꾸로(’ello’)를 호출합니다. 위와 같은 방식으로 문자가 1개가 될 때까지 진행합니다. 팩토리얼 함수와 마찬가지로 역순으로 다시 값을 대입하며 계산됩니다.

2. 나아가기

재귀함수는 병합정렬, 퀵정렬, 회문, 하노이의 탑 등 다양한 문제에 응용될 수 있습니다. 재귀함수는 반복하는 작업이 많아지고 복잡해질수록 강력하지만, 종료 조건이 충족되지 않는 경우 무한히 실행될 위험이 있으며 피보나치 수열처럼 같은 계산이 여러 번 되풀이되는 문제에서는 심각한 성능 낭비를 초래하게 됩니다.

아래 코드로 직접 확인해보세요. fib(30)을 구하는 데 fib(10)이 수십 번씩 다시 계산됩니다.

call_count = 0

def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(25))
print(f'함수 호출 횟수: {call_count}회')

이런 경우 이미 계산한 결과를 기억해두는 방법으로 해결할 수 있습니다. functools 모듈의 lru_cache 데코레이터를 붙이기만 하면 됩니다.

from functools import lru_cache

call_count = 0

@lru_cache
def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(25))
print(f'함수 호출 횟수: {call_count}회') # 호출 횟수가 극적으로 줄어듭니다.

이러한 이유로, 재귀함수를 작성할 때는 항상 종료 조건을 명확하게 정의하고, 꼭 필요한 경우가 아니면 반복문을 사용하여 재귀함수 대신 구현하는 것을 고려해보세요.