[BAEKJOON] 10872번 팩토리얼(Factorial) - 재귀

 

 

 

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

 

■ 1. 문제 분석 

(1) 문제 설명

* 팩토리얼(factorial): 양의 정수 n에 대해 그 수보다 작거나 같은 모든 양의 정수의 곱을 의미한다. 자연수의 계승이라고 한다. 기호는 느낌표(!)를 쓴다. 예를 들어, n의 팩토리얼은 n!로 나타낸다.
* ex) 4!=4×3×2×1=24

 

 

(2) 입출력 예시

▶ 입력 예시

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

10

 

▶  출력 예시

3628800

 

---

 

 

■ 2. 문제  풀이

(1) 방법 1  " 반복문 이용 "

 

 public void solution2() {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        in.close();

        int sum = 1;

        // N 이 0이 아닐 때 까지 1씩 감소하면서 sum에 반복적으로 곱해준다
        while(N != 0) {
            sum = sum * N;
            N--;
        }

        System.out.println(sum);
    }

 

 

(2) 방법 2  "재귀 함수 이용 "

public class Factorial_10872 {
    // 재귀문 사용
    public void solution1() {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        in.close();

        int sum = factorial(N);

        System.out.println(sum);

    }

    // 재귀 함수
    public static int factorial(int N) {
        // N이 1또는 0이 될 경우 return 1
        if(N <= 1) {
            return 1;	// 재귀 종료
        }

        return N * factorial(N - 1);
    }

 

▶문제 풀이

만일 N=5 이고 재귀함수로 5! 를 구하는 흐름은 이렇다.

순서	재귀함수 호출	재귀함수 진입	재귀 함수 반환 값	역순 계산
최초 호출	factorial(5)	5 x factorial(5 -1)	5 x factorial(4)	5 * 2 4(=4 * 3 * 2 * 1) = 120
2	factorial(4)	4 x factorial(4 -1)	4 x factorial(3)	4 * 6 (=3 * 2 * 1) = 24
3	factorial(3)	3 x  factorial(3 -1)	3 x factorial(2)	3 * 2 (=2 * 1) = 6
4	factorial(2)	2 x  factorial(2 -1)	2 x factorial(1)	2 * 1 = 2
5	factorial(1)		1	1

 

 

그림으로 쉽게 표현하면 이렇다. 

 

 

위 그림의 흐름을 이해하기 쉽게 과일 상자 비유를 통한 합 계산을 해보겠다. 

 

5개의 과일상자 있고,  각 상자는 현재 번호의 과일과 이전 상자를 포함하고 있으며, 마지막 상자는 과일 1개를 포함하고 있다고 해보자.

 

★ 팩토리얼 계산 과정:

• 합 계산 과정:
  • 첫 번째 상자(5)를 열면:
    • 내부에 두 번째 상자(4)가 있다.
    • 과일 수: 5 + (내부 상자에 포함된 과일 수)
  • 두 번째 상자(4)를 열면:
    • 내부에 세 번째 상자(3)가 있다.
    • 과일 수: 4 + (내부 상자에 포함된 과일 수)
  • 세 번째 상자(3)를 열면:
    • 내부에 네 번째 상자(2)가 있다.
    • 과일 수: 3 + (내부 상자에 포함된 과일 수)
  • 네 번째 상자(2)를 열면:
    • 내부에 다섯 번째 상자(1)가 있다.
    • 과일 수: 2 + (내부 상자에 포함된 과일 수)
  • 다섯 번째 상자(1)를 열면:
    • 내부에 더 작은 상자가 없고 과일 1개가 있다.
    • 과일 수: 1

 

각 상자를 모두 열었으니 연 상자를 닫으면서 내부 상자의 과일 수를 더해보자.

 

★  계산 역추적:

• 다섯 번째 상자(1)의 과일 1개를 네 번째 상자(2)에 더한다.
  • 과일 수: 2 + 1 = 3
• 네 번째 상자(2)의 과일 3개를 세 번째 상자(3)에 더한다.
  • 과일 수: 3 + 3 = 6
• 세 번째 상자(3)의 과일 6개를 두 번째 상자(4)에 더한다.
  • 과일 수: 4 + 6 = 10
• 두 번째 상자(4)의 과일 10개를 첫 번째 상자(5)에 더다.
  • 과일 수: 5 + 10 = 15

 

결과적으로, 5개의 과일 상자를 모두 열어 최종적으로 15개의 과일을 얻는다. 이런식으로 재귀함수를 이해하면 쉽다!