모두의 알고리즘 문제 04. 팩토리얼 구하기

팩토리얼을 구하는 알고리즘 1

def fact(n):
    f=1 #결과 저장 변수f
    for i in range (1,n+1): #1부터 n+1 미만까지
        f= f*i
        print(n, f)
    return f

print(fact(1))
print("")
print(fact(3))
print("")
print(fact(10))

각 단계마다 무슨 값을 가지는지 보기 쉽게 print함수를 몇개 추가했다. 결과는 아래와 같다.

 

1 1
1

3 1
3 2
3 6
6

10 1
10 2
10 6
10 24
10 120
10 720
10 5040
10 40320
10 362880
10 3628800
3628800

Process finished with exit code 0

 

입력n이 1일 때 1에 1을 곱하고 결과는 1.

입력n이 3일 때 1에 1을 곱하고, 2를 곱하고, 3을 곱해서 결과는 6.

입력n이 10일 때도 마찬가지로 1부터 10까지 차례대로 곱한 후 결과를 출력한다.

 

위의 코드는 재귀 호출 방식이 아니다. 재귀 호출 방식으로 팩토리얼을 구하는 알고리즘을 만들어보자.

 

 

팩토리얼을 구하는 알고리즘 2 - 재귀 호출 방식 사용

def fact(n):
    if n <= 1:
        print("x", 1)
        return 1
    print("x", n )
    return n * fact(n-1)

print("결과:", fact(1))
print("")
print("결과:",fact(5))
print("")
print("결과:",fact(10))

이번에도 알고리즘이 돌아가는 과정을 알기 쉽게 print문 몇개를 삽입했다. 

 

처음 봤을 땐 어떻게 구해지는거지? 하고 어리둥절 했다. 대충 어렴풋이 어떤식인지는 감을 잡았고 교재에 설명이 자세히 써져있어서 금방 이해됐다. 어떻게 이걸 만든건지 대단하다.

 

결과는 아래와 같다.

 

x 1
결과: 1

x 5
x 4
x 3
x 2
x 1
결과: 120

x 10
x 9
x 8
x 7
x 6
x 5
x 4
x 3
x 2
x 1
결과: 3628800

Process finished with exit code 0

 

위 결과의 'x 10', 'x 9' 등은 해당하는 숫자의 팩토리얼을 호출할 때 출력된다. fact(10)을 호출했을 때 'x 10' 출력, fact(10)은 fact(9)를 호출하여 fact(9)가 실행되고 'x 9'가 출력. 이런식으로 각 함수가 호출될 때마다 차례대로 출력된다.

이후 fact(1)까지 내려간 후에 fact(1)에서부터 값을 반환받아 fact(2)부터  fact(10)까지 차례대로 값을 반환하며 올라오고 fact(10)에서 '결과: n * fact(n - 1)'을 반환한다.

 

작동방식을 설명해보겠다.

 

1. 5를 입력했다고 해보자. fact(5) 호출.

 

2. fact(5) 즉 5!은 5 * 4!이다. 파이썬으로 표현하자면 [fact(5) == 5 * fact(4)] 

 

3. fact(4) 값을 알아야 fact(5)를 구할 수 있으므로 fact(4) 호출.

 

4. fact(4)는 fact(3)을 알아야 구할 수 있으므로 fact(3)을 호출, fact(3)은 fact(2)를 호출, fact(2)는 fact(1)을 호출한다.

 

5. fact(2)가 호출한 fact(1)은 조건문에 걸려서 1을 반환한다. 

 

6. 1을 반환받은 fact(2)는 값을 fact(3)에 반환한다. fact(3)도 3 * fact(2)인 상황에서 fact(2) 값을 반환받아서 3!을 계산하고 값을 fact(4) 에 반환한다. fact(4)도 4!값을 fact(5)에 반환한다.

 

7. fact(5)가 값을 반환한다.

 

 

 

for를 사용한 알고리즘, 재귀 호출을 사용한 알고리즘은 빅 오 표기법으로 어떻게 표현할 수 있을지 알아보자.

 

for 반복문을 이용한 알고리즘의 경우 n!을 구하려면 곱셈이 n번 필요하다. 1!은 1번, 10!은 10번.

 

재귀 호출을 이용한 알고리즘의 경우 fact(4)를 구하려면 fact(1)에서 1을 반환받은 후 fact(2)에서 반환, fact(3)에서 반환, fact(4)에서 반환, 총 3번의 곱셈이 필요하다. 즉, fact(n)을 구하기 위해서 n-1 번의 곱셈이 필요하다.

 

for 반복문, 재귀 호출 두 경우 모두 입력값의 크기와 알고리즘 시간이 비례한다. 따라서 알고리즘의 시간 복잡도는 O(n)이다.

 

 

끝으로, 교재에서 강조하는 중요한 점은 재귀호출을 사용할 때는 반드시 '종료 조건'이 필요하다는 것이다. 종료 조건이 없으면 재귀 에러나 스택 오버플로 등 프로그램 에러가 발생해 비정상적인 동작을 할 수도 있다.