팩토리얼(factorial) 이란?

1부터 n까지 연속한 정수의 곱을 구하는 알고리즘 ( n! )
단, 0!은 1이다.

코드 구현 (재귀 X)

def fact(n):
	f = 1 			#곱을 계산할 변수의 초깃값
    for i in range(1, n+1): 	# 1부터 n까지 반복
    	f = f * i 		# 곱셈 연산
    return 1

팩토리얼을 재귀적 호출로 표현하면 다음과 같다.

1! = 1
2! = 2 x 1 = 2 x 1!
3! = 3 x (2 x 1) = 3 x 2!
4! = 4 x (3 x 2 x 1) = 4 x 3!
...
n! = n x (n-1)!

팩토리얼을 구하려고 다시 팩토리얼을 구한다(재귀적 정의).

코드 구현 (재귀 O)

def fact(n):
	if n <= 1: 	# n이 1 이하이면 종료조건
    	return 1 	# 결과 값을 1로 돌려준다
    return n * fact(n-1)

재귀함수를 사용한 코드 분석

fact(4)를 호출했을 때를 생각해보자!

1. fact(4)는 4 x fact(3) 이므로 fact(3)을 호출
2. fact(3)는 3 x fact(2) 이므로 fact(2)을 호출
3. fact(2)는 2 x fact(1) 이므로 fact(1)을 호출
4. fact(1)은 종료 조건이므로 fact() 함수를 더 이상 호출하지 않고 1을 돌려준다.
5. fact(2)는 fact(1)에서 돌려받은 결과값 1에 2를 곱해 2를 돌려준다.
6. fact(3)는 fact(2)에서 돌려받은 결과값 2에 3를 곱해 6를 돌려준다.
7. fact(4)는 fact(3)에서 돌려받은 결과값 6에 4를 곱해 24를 돌려준다. >> 최종 결과

n!을 구하려면 곱셈이ㅣ n-1번 필요함을 위의 예제를 통해 확인할 수 있다.

따라서 재귀 호출을 이용한 알고리즘의 계산 복잡도는 모두 O(n)