재귀 알고리즘 - 팩토리얼 계산 이해와 효율적인 구현 방법

팩토리얼 개요

• 주어진 양의 정수 n에 대해 1부터 n까지의 모든 양의 정수의 곱을 의미합니다.
• 정수 n에 대해 n!으로 표기됩니다.

팩토리얼 동작원리

• n이 0이거나 1일 경우에는 팩토리얼 값이 1이므로, 1을 반환합니다.
• 그렇지 않을 경우에는 n에 대해 n-1의 팩토리얼을 구한 뒤, n과 곱하여 반환합니다.

팩토리얼 코드 예시

function factorial(n) {
 if(n === 0 || n === 1) return 1
 return n * factorial(n-1)
}

 

팩토리얼 코드 호출 순서

• factorial(3)일 경우 3 * factorial(2) -> 2 * factorial(1) -> return 1 -> return 2 * 1 -> return 3* 2 = 6

팩토리얼 시간 복잡도

• n의 값이 1씩 감소하면서 재귀 호출이 이뤄지기때문에 시간복잡도는 O(n)입니다.