[Java] 백준알고리즘 #27433 팩토리얼 2

백준알고리즘 #27433 팩토리얼 2

재귀함수를 사용해 팩토리얼 값을 계산하는 문제.

 

n! 은 n x (n-1)! 로 나타낼 수 있고, (n-1)! 은 다시 (n-1) x (n-2)! 로 나타낼 수 있다.

여기서 !(팩토리얼)을 어떤 함수 fact라고 한다면,

n!은 fact(n)이고, 이는 n x fact(n-1)이 될 것이다.

 

위 fact함수에서 n이 1이 될 경우 fact(1) 은 1 x fact(0) 가 되어 결과가 0이 되어버릴 것이다.

뿐만 아니라, 위 과정을 반복하다보면 n x (n-1) x ... x 2 x 1 x 0 이 될 것이고, 이는 음수로 무한히 이어지게 된다.

따라서 재귀함수에서는 종료조건을 반드시 명시해주어야 한다.

때문에 조건문을 통해 n이 1보다 큰 경우로 한정하고, 1 이하가 되는 경우에는 x 1로 자기 자신을 리턴하면 된다.

 

입력이 0인 경우 1이 되는것에 주의하여 코드를 작성해보면 다음과 같다.

// 해설참조 : sehyeok.tistory.com 

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long res;				// 결과값 담을 변수
        if (n == 0) {				// n이 0이면 결과는 1
            res = 1;
        } else {
            res = fact(n);			// 함수호출
        }
        System.out.println(res);
        br.close();
    }

    public static long fact(long n) {
        if (n > 1) {
            n = n * fact(n - 1);	// 자기자신 호출(재귀)
        } else {
            n = n * 1;			// n이 1이 될 때 (재귀함수 종료 조건 충족)
        }

        return n;
    }

}

 

또는 다음과 같이 0이 되는 경우를 fact함수 안에서 정의해 줄 수도 있다.

 

// 해설참조 : sehyeok.tistory.com 

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println(fact(n));
        br.close();
    }

    public static long fact(long n) {
        if (n == 0) {		// 입력이 0인경우 출력은 1
            return 1;
        }
        if (n > 1) {
            n = n * fact(n - 1); // 자기자신 호출(재귀)
        } else {
            n = n * 1; 		// n이 1이 될 때 (재귀함수 종료 조건 충족)
        }

        return n;
    }

}