JAVA 백준 문제풀이 (14) 10872: 팩토리얼

 

가장 기초적인 팩토리얼 문제이다.

사실 팩토리얼은 for문으로 풀어도 아무런 문제가 없으나, 백준에서 해당 문제가 재귀 카테고리에 올라가 있었기 때문에 재귀를 활용해서 풀었다. 

재귀란 무엇인가?

 

재귀
어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 
자기언급과도 관련된 재귀는 언어학에서 논리학에 이르기까지 다양한 분야에서 연구되는 주제로, 특히 컴퓨터 과학과 수학에서, 재귀는 함수가 자신의 정의에 의해 정의될 때의 개념을 가리킨다.
<wikipedia>

 

쩝.. 처음 접하면 어렵게 느껴질 수도 있다.

하지만 사칙연산만 할 수 있다면 누구나 이해할 수 있는 것이니 밑을 보자.

 

 

늘 악필 죄송합니다.

팩토리얼 N! = n-2 * n이라는 공식을 갖는다.

그러니까, 팩토리얼(3) = 팩토리얼(2)의 결과 * 3이란 말이다.

 

엥? 이거 완전 메서드 아니냐?

맞습니다.

 

저 공식 자체가 이미 재귀적인 공식이고 자바에 입력할 코드 그 자체이다.

만약 N!에 4를 넣는다고 생각해보자. factorial(4)는 어떻게 구할 수 있는가?

factorial(3)과 4의 곱이 factorial(4)이다.

그런데 이를 구하기 위해서는 그 안에서 factorial(3)을 구해야 한다.

factorial(3)은 factorial(2)와 3의 곱이다.

이렇게 내려오다보면 factoral(2)까지 내려와서 2 * 1을 만나게 된다.

 

이제 더이상 내려갈 곳이 없으니 다시 거슬러 올라간다.

factorial(3)은 3*factorial(2)인데 방금 전의 결과로 우리는 factorial(2)가 2라는 사실을 알고 있다.

factorial(4)는 4*factorial(3)인데 방금 전의 결과로 우리는 factorial(3)이 6이라는 사실을 알고 있다.

그러면 결과적으로 factorial(4)는? 24가 나온다.

 

이제 이걸 코드로 표현해보자.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
    // Scanner, BufferdReader는 취향대로 고르면 된다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(factorial(n));
    }
    // 팩토리얼을 구하는 재귀 메서드
    static int factorial(int num) {
        if (num == 0 || num == 1) {
        // 팩토리얼에서 !0과 !1의 결과는 1로 정해져 있다
            return 1;
        } else {
        // 따라서 factorial(2)가 나올 때까지 내려가며 계산한 뒤
        // 해당 값을 리턴 받으면 거슬러 올라오며 factorial(num)의 값을 반환함
            return num * factorial(num-1);
        }
    }
}

 

 

좋다 좋아.