팩토리얼(계승)이란?
10 이하의 숫자 n이 주어졌을 때, 해당 숫자의 팩토리얼(계승)을 구하는 문제를 생각해 보겠습니다. 숫자 n의 팩토리얼은 다음과 같이 정의됩니다.
n! = n × (n-1) × (n-2) × ... × 1
예를 들어, 입력값이 6이라면 6 × 5 × 4 × 3 × 2 × 1의 계산 결과인 720이 출력됩니다.
문제 해결 접근 방법
이 문제는 재귀 함수를 사용하면 간단하게 해결할 수 있습니다. 해결 과정은 다음과 같습니다.
solve()함수를 정의하고, 매개변수로 n을 받습니다.- n이 1 이하이면 1을 반환합니다. (재귀 호출의 종료 조건, 즉 기저 사례)
- 그렇지 않으면
n * solve(n - 1)을 반환하여 자기 자신을 재귀적으로 호출합니다.
구현 예제
다음 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, n):
if(n <= 1): return 1
return n * self.solve(n - 1)
ob = Solution()
print(ob.solve(6))
입력
6
출력
720
코드 동작 원리
이 코드의 핵심은 재귀 호출입니다. solve(6)이 호출되면 내부적으로 다음과 같은 과정으로 계산이 진행됩니다.
- solve(6) → 6 × solve(5)
- solve(5) → 5 × solve(4)
- solve(4) → 4 × solve(3)
- solve(3) → 3 × solve(2)
- solve(2) → 2 × solve(1)
- solve(1) → 1 (종료 조건에 도달)
각 호출이 차례로 반환되면서 최종적으로 6 × 5 × 4 × 3 × 2 × 1 = 720이 계산됩니다.
참고: 성능과 대안
이 알고리즘의 시간 복잡도는 O(n)이며, 재귀 호출 깊이 역시 n에 비례합니다. 따라서 n이 매우 큰 경우에는 Python의 재귀 깊이 제한(기본 1000)에 도달할 수 있으므로, 반복문 방식이나 표준 라이브러리의 math.factorial() 함수를 사용하는 것이 더 안전하고 효율적입니다.