[Python] '팩토리얼' 알고리즘

본문은 <모두의 알고리즘 with 파이썬>(길벗, 2017)을 학습하고 개인 학습용으로 정리한 내용입니다.

 

안녕하세요, 오늘은 Python으로 '팩토리얼' 알고리즘 구현하는 법에 대해 알아보겠습니다.

팩토리얼은 숫자 뒤에 느낌표(!)를 붙여 표기하며 1부터 n까지 연속한 숫자를 차례로 곱한 값을 말합니다. '계승'이라고도 합니다.

 

크게 2가지 방법으로 '팩토리얼' 알고리즘을 구현해보겠습니다.

1. 반복문을 이용해서 작성하는 법

2. 재귀함수를 이용해서 작성하는 법

---

#1. 반복문을 이용

def sum_multiply(n):
    sum_m = 1
    for i in range(1, n + 1):
        sum_m = sum_m * i
    return sum_m

 

0. sum_multipy라는 함수 선언, 함수의 인자로 n을 받음

 

1. 팩토리얼 결과를 담을 변수 sum_m을 1로 초기화

 

2. for문을 활용해서 n번 반복문 실행, range 함수를 사용해서 1부터 n까지의 값을 변수 i로 받음

 

3. sum_m 변수에 i를 곱해주고 다시 sum_m 변수에 값을 할당

 

4. 반복문을 마치고 sum_m 변수를 반환

 

---

#2. 재귀함수 이용

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n-1)

 

0. fact 함수의 인자로 n을 받음

 

1. 재귀함수의 종료조건 'n <= 1'일 때 1을 반환하도록 함

 

2. n * fact(n-1)을 반환

 

위 코드를 말로 풀어쓰면 아래와 같다.

 

우선 n이 1 이하인지 비교한다.

- 1 이하는 아주 작아서 더는 계산하지 않아도 되는 '종료 조건'이다.

- 이때 1을 결과값으로 돌려준다

 

n이 1보다 크면 n! = n * (n-1)!이므로 n * fact(n-1)을 결과값으로 둘려준다

이 과정에서 n!을 구하기 위해서 더 작은 값인 (n-1)!을 구하는 fact(n-1)이 재귀 호출된다.

 

fact(n)을 풀기 위해서 fact(n-1)을 재귀 호출하였는데 호출된 fact(n-1)은 다시 종료 조건에 해당하는지 확인한다. 종료 조건이 아니라면 이번에는 fact(n-2)를 호출한다. 

 

마찬가지로 fact(n-3), fact(n-4)... 이렇게 반복하다 보면 결국 fact(1)을 만나게 된다. 따라서 재귀호출이 영원히 반복되지 않고 결국 답을 얻게 된다.

---

오늘은 여기까지입니다. 다음 번에 또 다른 알고리즘으로 찾아 뵙겠습니다~