재귀 함수(recursive function)란 함수가 실행되는 도중에 자기 자신을 다시 호출하는 함수를 말합니다. 이러한 구조 덕분에 함수는 여러 번 반복적으로 실행되며, 각 반복이 끝날 때마다 결과를 출력할 수 있습니다. 재귀는 무한대의 개념과도 깊은 연관이 있는데, 마치 서로 마주 본 두 거울 사이의 물체가 무한히 반사되는 것과 비슷한 원리입니다.
재귀 함수의 대표적인 예: 팩토리얼
재귀 함수를 설명할 때 가장 많이 사용되는 예시가 바로 팩토리얼(factorial)입니다. 어떤 수의 팩토리얼이란 1부터 그 수까지의 모든 정수를 곱한 값을 의미합니다.
예를 들어, 9의 팩토리얼(9!로 표기)은 다음과 같이 계산됩니다.
9! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 = 362880
예제 1: 팩토리얼을 구하는 재귀 함수
def factorial(i):
if i == 1:
return 1
else:
return (i * factorial(i-1))
number = 9
print("The factorial of", number, "is", factorial(number))실행 결과
The factorial of 9 is 362880
위 프로그램에서 factorial() 함수는 자기 자신을 호출하므로 재귀 함수입니다. 각 함수 호출은 현재 숫자와 '그 숫자에서 1을 뺀 값의 팩토리얼'을 곱하는 방식으로 동작하며, 숫자가 1이 되면 재귀 호출을 멈추고 최종 결과를 반환합니다.
쉽게 비유하자면, 서로 마주 보게 놓인 두 개의 평행한 거울을 상상해 보세요. 그 사이에 놓인 물체는 거울 사이에서 무한히 재귀적으로 반사되어 나타나는 것처럼 말입니다.
예제 2: 숫자를 내림차순·오름차순으로 출력하는 재귀 함수
다음 예제는 재귀 호출 전후에 각각 출력문을 배치하여, 숫자가 감소했다가 다시 증가하는 과정을 확인할 수 있게 만든 코드입니다.
def Function(x):
if (x < 1):
return
else:
print(x, end = " ")
Function(x-1)
print(x, end = " ")
return
x = 5
Function(x)실행 결과
5 4 3 2 1 1 2 3 4 5
이 코드의 동작 원리를 살펴보면, 먼저 5부터 1까지 숫자가 순서대로 출력된 후, 재귀 호출이 종료되며 스택이 되감기면서 1부터 5까지 다시 출력됩니다. 이처럼 재귀 함수는 호출 시점 이전과 이후에 각각 다른 작업을 수행할 수 있어, 다양한 알고리즘 문제 해결에 활용됩니다.
정리
재귀 함수는 문제를 더 작은 단위로 나누어 해결하는 강력한 도구입니다. 다만 종료 조건(base case)을 명확히 설정하지 않으면 무한 호출로 인한 오류가 발생할 수 있으므로, 항상 재귀를 멈출 조건을 신중하게 설계하는 것이 중요합니다.