[백준] 10872번 재귀 함수 이용해서 풀기 (feat. 재귀 함수란?)

문제의 제목은 "팩토리얼" 이다.

문제

0보다 크거나 같은 정수 N이 주어진다. 이때 N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 <= N <= 12)이 주어진다.

출력

첫째 줄에 N!을 출력한다.

예제 입력1

10

예제 출력2

3628800

예제 입력2

0

예제 출력2

1

 

문제풀이 코드

# 재귀함수를 이용한 코드
n = int(input())
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)

print(factorial(n))

 

문제풀이

우선, 이 문제는 백준저지의 단계별 풀어보기 문제집에서 "재귀" 파트에 있는 문제이다.
따라서 재귀를 이용하여 풀어볼 것을 권한다.

이 문제는 크게 2가지 방법으로 문제를 풀어 볼 수 있다.

• for문
• 재귀 함수

우선은 for문을 이용하여 코드를 작성해보자.

[for문 이용한 문제 풀이]

# for문 이용한 코드
n = int(input())
def factorial(n):
    n_fac = 1
    for i in range(1, n+1):
        n_fac = n_fac * i
    print(n_fac)

factorial(n)

n_fac 이라는 변수를 선언 해 주었다. 초기값을 1로 설정한 이유는, 팩토리얼의 성질로인해 0! = 1 이기 때문에 이를고려하여 초기값을 1로 설정했다. 초기값을 1로 설정함으로 인해 n=0 일때에도 0!의 정답인 1이 출력되게 된다.

전체적인 코드실행과정을 살펴보면 입력을 n이라는 변수에 받고,
n_fac 변수의 초기값은 1로 설정한 상태로

for i in range(1, n+1):

을 통해 팩토리얼 곱셈이 실행되며 각 루프의 결고값은 계속해서 n_fac 변수에 할당되어 해당 루프의 index i 와 곱해진다.
입력변수 n에따라 정해진 루프를 돌고나면, print(n_fac)을 통해 팩토리얼 계산의 결과값이 출력된다.

 

근데, 이 문제는 앞서 말했듯, 백준 저지의 단계별 문제집에서 "재귀"파트에 있는 문제이다.
따라서 이번에는 재귀함수를 이용하여 문제를 풀어 볼 것이다.

[재귀 함수를 이용한 문제 풀이]

# 재귀함수를 이용한 코드
n = int(input())
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)

print(factorial(n))

우선, 재귀함수가 무엇인지에 대해 간략히 소개하도록 하겠다.

• 재귀 함수란?

재귀 함수(Recursive Function)란, 자기 자신을 다시 호출하는 함수를 의미한다.

• 단순한 형태의 재귀 함수 예제
  • '재귀 함수를 호출합니다.' 라는 문자열을 무한히 출력한다.
  • 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.

def recursive_function():
	print('재귀 함수를 호출합니다.')
	recursive_function()
    
recusive_function()

재귀 함수

별도의 설정을 해주지 않으면, 재귀 함수는 제한된 최대깊이에 도달하면 오류메시지가 나오게 된다.
일반적인 형태의 알고리즘 테스트의 수준에서는 일반적인 재귀 함수를 사용해도 통과할 수 있도록 출제되는 경우가 많다.

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.

종료조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.
이번에는 종료 조건을 포함한 재귀 함수 예제를 알아보자.

 

# 종료구문이 포함된 재귀 함수
def recursive_function(i):
    # 10번쨰 호출을 했을 떄 종료되도록 종료 조건 명시
    if i == 10:
        return
    print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀함수를 종료합니다.')

recursive_function(1)

종료구문이 있는 재귀 함수

print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')을 실행하고,
i가 10이 될때까지  recursive_function(i+1)을  호출한다.

i가 10이 되면 종료구문을 만나고, 해당 종료구문에 의해, 자기자신을 호출했던 함수로 돌아가게 되는데, 
돌아가면, 해당 재귀함수의 두번쨰 print문을 실행하고 또 자기자신을 호출했던 재귀함수로 돌아가서 두번째 print문을 실행하는 것을 반복하여 i가 1일때의 두번쨰 print문 실행까지 완료하게 된다.

[ 이 문제의 코드 풀이]

# 재귀함수를 이용한 코드
n = int(input())
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)

print(factorial(n))

이 문제를 풀이한 코드는 다음과 같다.

우선 n이라는 변수로 입력을 받는다
그리고나서 factorial(n)을 실행하는데,
만약에 n이 5라면,
n*factorial(n-1) 구문에 의해 n이 1씩 줄어들며 재귀함수를 호출하다가 n이 1이되면 재귀 호출을 종료하게 된다.
그러면 그때부터 다시 자기자신을 호출했던 함수로 돌아가게 되는데,
1을 호출했던 factorial(1)을 호출했던 factoriacl(2)을 호출했던 factorial(3)을 호출했던 factorial(4)을 호출했던 factorial(5)로 돌오가며 1 * 2 * 3 * 4  * 5 이 최종 결과가 된다.