5알고리즘 분석
팩토리얼은 연속한 수의 곱이므로 곱셈의 횟수를 기준으로 알고리즘 분석을 해 보겠습니다.
for 반복문을 이용한 프로그램 4-1의 경우 n!을 구하려면 곱셈이 n번 필요합니다. 그렇다면 재귀 호출 알고리즘으로 만들어진 프로그램 4-2는 어떨까요?
종이에 연필로 쓴 fact(4) 계산 과정을 보면 힌트가 보입니다. fact(4)를 구하려면 fact(1)의 종료 조건으로 돌려받은 1을 2와 곱하여 돌려줍니다. 그리고 그 값에 다시 3을 곱하여 돌려주고, 다시 그 값에 4를 곱하여 돌려주므로 곱셈이 모두 세 번 필요합니다. 마찬가지로 n!을 구하려면 곱셈이 모두 n-1번 필요하다는 것을 알 수 있습니다.
따라서 반복문을 이용한 알고리즘이나 재귀 호출을 이용한 알고리즘의 계산 복잡도는 모두 O(n)입니다.
잠깐만요
재귀 호출의 일반적인 형태
재귀 호출을 이용해서 문제를 풀 때는 보통 다음과 같은 구조로 알고리즘을 만듭니다.
def func(입력 값):
if 입력 값이 충분히 작으면: # 종료 조건
return 결괏값
...
func(더 작은 입력 값) # 더 작은 값으로 자기 자신을 호출
...
return 결괏값
재귀 호출에는 종료 조건이 필요하다는 사실을 꼭 기억하세요. 종료 조건이 없으면 재귀 에러(RecursionError)나 스택 오버플로(Stack Overflow) 등 프로그램 에러가 발생해 비정상적인 동작을 할 수도 있습니다.