견고한 파이썬 | 위니북스

재귀함수

1. 재귀함수(recursion)

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

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

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

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

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

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

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

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

💡 실제로 재귀는 무한 반복되지 않고 1000번만 가능합니다. colab에서는 이보다 적은 숫자인 958번 재귀로 호출할 수 있습니다. sys.setrecursionlimit로 이 제한을 풀 수 있습니다.

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

# 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

# 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

# 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'

# 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. 나아가기

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

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

{"packages":["numpy","pandas","matplotlib","lxml"]}