[python] 백준 10872 : 팩토리얼

아마 시중에 떠도는 알고리즘책을 보시면 보통 앞쪽부분에 알고리즘 기초를 논하면서 가장 많이 예시로 드는 문제중 하나일겁니다. 저는 재귀호출을 사용하는 구조에대해 논해보렵니다. 이 문제는 반복문 재귀문 둘다 사용가능합니다.

 

뭐 for문을 쓰면 아주 간단히 아래와같이 구현할수있을겁니다.

n=int(input())

def fact():
    k=1
    for i in range (1,n+1):
        k=i*k
    return k

print(fact())

n을 입력받아 n!을 구합니다. i는 1부터 n까지 차례로 반복되며 k의 값에 곱해집니다.

i=1일때 k=1, i=2일때 k=2*1, i=3일때 k=3*2 이런식으로 한번 k에 곱해진후 for문의 처음으로 돌아가 i+1이 되어 곱해지는 동작을 i=n이 될때까지 반복수행합니다. 1부터 n까지 합을구하는 방식과 비슷하죠?

이렇게 반복문을 쓰는것도 낫베드입니다.

 

그러나 저는 조금 있어보이게 재귀호출도 사용해보겠읍니다. 사실 저의 아주 귀여운 코딩실력을 보시면 아시겠지만... 

def를 잘 못안쓰는데 def 함수정의를 능숙히 할줄알면 코딩이 훨씬 깔끔하고 간단해집니다. 같이 연습해봅시다.

 

재귀호출이란 함수가 자기 자신을 부르는것입니다. 약간 합성함수 f(f(x))비숫한 느낌이죠. (수능친지 n년 넘은 틀딱인데 합성함수라는 단어가 되게 오랫만이네요 사실 명칭 기억안나서 좀 얼탐)

재귀호출을 설명할때 주로 드는 예시로 마트료시카가 있는데요, 꽤나 적절한 예시라고 생각합니다. 특히 이 팩토리얼 문제에서요. n!은 n-1!에 n을 곱한것입니다. 이때 n-1!은 또 n-2!에 n-1을 곱한것이죠. 이게 계속 반복됩니다. n이 점점 작아지지만 구조상으로는 동일한, 변수는 점점 귀여워지지만 동일한 함수입니다. 마치 큰 인형을 까보면 작은인형이 계속 반복되는 마트료시카처럼요.

 

재귀호출은 순차적인 변수를 이용해 동일한 매커니즘으로 계산을 해야하는 구조에서 유용하게 쓰일수있습니다.

 

재귀호출에서 또 중요한것은 종료조건입니다. 위에서 n!이 n-1!xn이고, 이때 n-1!은 n-2!xn-1이고...! 이게 계속 반복된다고 했는데 어디까지 반복될까요? 반복조건을 설정하지 않는다면 재귀문은 무한히 반복하다가 결국 혼자 오류 출력하면서 거품물고 쓰러집니다. 컴퓨터도 좀 아파하구요. 또한 우리가 구하려는 팩토리얼은 1부터 시작하는 정수의 곱들이니 무한히 반복하는것은 옳지않겠죠. 종료조건을 줘서 적절한 타이밍에 끊어줘야합니다. 

 

주저리주저리 떠들어댔는데 이론적인 설명이었구요 코딩을 보면서 조금더 얘기해보겠습니다.

n=int(input())

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

이거시 재귀호출을 이용한 팩토리얼 함수입니다.

n <= 1일때 1을 반환한다는것은 위에서 말한 종료조건입니다. 재귀가 반복될수록 n이 점점 작아지다 1이될때부턴 그냥 1만 곱해주므로 사실상 n=1부턴 더이상 계산할 필요가없는, 종료선언이죠

 

그외의 경우에는 반환값이 n*fact(n-1)로, fact함수안에 fact가 들어가있습니다. 위에서 말했듯 n! = n-1! x n으로 표현한것이죠. 이제 저 fact(n-1)안에서는 또 fact(n-1) = fact(n-2) x n-1이 되며 이때는 n x n-1 x fact(n-2)가 되는것이죠. 또 한번 반복된다면 n x n-1 x n-2 x fact(n-3)이되는거구요. 이게 1까지 반복된다면 우리가 아는 n!의 값이 구해지겠지요.

 

def 함수이름 () 에서 위에 for문을 이용할때와는 달리 괄호안에 변수인 (n)을 입력해줬는데요, 그 이유는....

위에 함수엔 변수에 그냥 안넣었구요...(;;) (사실 return이 중요한것이기땜에 상관읎읍니다. 저 윗구문에서 def는 계산적 기능이 크게 없기때문에 상관없어요. 걍 def안하고 for문만 해도됌)

아래에선 다음함수의 n자리에는 n-1을 대입해야하기때문에 이땐 변수를 한번 확인해주는것이 필요했습니다.

 

이 문제를 기반으로 재귀문을 사용할수있는 구조인지 아닌지를 파악해보는것도 좋을거같읍니다.