Python | 재귀호출

재귀호출이란?

함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출(recursive call)이라고 한다.

일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용하다. 재귀호출은 코드가 간단한 편이지만 머릿속으로 생각을 많이 해야 한다.

재귀호출 함수 만들기

간단한 재귀호출 함수를 만들어보자.

def hello():
    print('Hello, world!')
    hello()
 
hello()

소스 코드를 실행해보면 'Hello, world!' 문자열이 계속 출력되다가 에러가 발생한다. 왜냐하면 파이썬에서는 최대 재귀 깊이(maximum recursion depth)가 1,000으로 정해져 있어서 그렇다. 즉, hello 함수가 자기자신을 계속 호출하다가 최대 재귀 깊이를 초과하면 RecursionError가 발생한다.

종료조건 만들기

재귀호출을 사용하려면 반드시 종료 조건을 만들어주어야 한다.

def hello(count):
    if count == 0:    # 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄
        return
    
    print('Hello, world!', count)
    
    count -= 1      # count를 1 감소시킨 뒤
    hello(count)    # 다시 hello에 넣음
 
hello(5)    # hello 함수 호출

Hello, world! 5
Hello, world! 4
Hello, world! 3
Hello, world! 2
Hello, world! 1

재귀는 처음에 어렵게 느껴질 수 있지만, 언제 자기 자신을 호출할 것인지, 어떤 값을 변화시켜 매개변수로 전달할 것인지를 잘 신경쓰면 쉽게 작성할 수 있다.

재귀호출 활용하기

팩토리얼 구하기

팩토리얼은 1부터 n까지 양의 정수를 차례대로 곱한 값이며 !(느낌표) 기호로 표기한다. 예를 들어 5!은 5 4 3 2 1이며 결과는 120이다.

def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
 
print(factorial(5))

120

피보나치 수 구하기

피보나치 수열은 1, 1, 2, 3, 5, 8, … 순으로 앞의 두 수를 합한 수를 나열한 수열이다. 예를 들어 다섯 번째 피보나치 수는 세 번째 수 2와 네 번째 수 3의 합이다.

다음 세 가지 규칙만 알면 몇 번째 피보나치 수라도 계산할 수 있다.

• 규칙 1: 첫 번째 피보나치 수는 1
• 규칙 2: 두 번째 피보나치 수는 1
• 규칙 3: 그 후, N 번째 피보나치 수는 (N - 1) 번째 피보나치 수와 (N - 2) 번째 피보나치 수의 합

def n번째_피보나치_수(n):
    """n번째 피보나치 수를 반환한다."""
    if n == 1:     # 첫 번째 피보나치 수는 1
        return 1
    elif n == 2:   # 두 번째 피보나치 수는 1
        return 1
    else:          # 그 후의 피보나치 수
        return n번째_피보나치_수(n - 1) + n번째_피보나치_수(n - 2)

# 1번째부터 11번째 피보나치 수까지 출력
for n range(1, 12):
    print(n번째_피보나치_수(n), end=' ')

본 포스팅은 아래의 사이트를 참고하여 작성되었습니다.
연오의 파이썬 https://python.bakyeono.net/chapter-6.html
코딩도장 https://dojang.io/