자기 스스로를 호출하는 재귀 함수

재귀 함수(Recursive function)는 함수 내부에서 자기 자신을 호출하며, 특정 조건(종료 조건)이 충족될 때까지 반복적으로 실행되는 함수를 뜻합니다.

아래는 1부터 전달받은 숫자까지의 곱을 계산하는 재귀 함수의 예시입니다.

복사
# n! = 1 * 2 * 3 * ... * n
def factorial(n):
    # n이 1일 때, 종료 조건
    if n == 1:
        # 1을 반환하고 재귀 호출을 끝냄
        return 1
    else:
        # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
        return n * factorial(n - 1)

# 함수 호출
print(factorial(5))
# 120

재귀 함수는 1부터 n까지의 곱을 계산하는 팩토리얼(!), 피보나치 수열(두 수의 합이 다음 수가 되는 수열) 등 반복적인 작업을 수행할 때 사용합니다.

또한 데이터를 탐색하거나 조작할 때 사용하는 알고리즘에서도 재귀 함수를 사용할 수 있습니다.

복사
def fibonacci(n):
    # n이 1 이하일 때, n을 반환
    if n <= 1:
        return n
    # n이 2 이상일 때
    else:
        # n-1번째와 n-2번째 피보나치 수열의 합을 반환
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(6))
# 8