자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 팩토리얼

 

https://hyejin.tistory.com/1254

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 이진수 출력

-> 이전 문제 풀이 

 

 

3. 팩토리얼 

설명

자연수 N이 입력되면 N!를 구하는 프로그램을 작성하세요.

예를 들어 5! = 5*4*3*2*1=120입니다.

 

입력

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

 

출력

첫 번째 줄에 N팩토리얼 값을 출력합니다.

 

예시 입력 1 

5

 

예시 출력 1

120

 

 

 

문제 풀이 1

public int DFS(int n) {
    if (n != 1) {
        return n * DFS(n - 1);
    }else {
        return 1;
    }
}

 

👾 : 재귀 함수 기초 문제 푸는데 팩토리얼 문제는 항상 필수로 나오는 예제인 것 같다. ㅋㅋ 

아무튼 팩토리얼은 5! 이다. 하면 5 * 4 * 3 * 2 * 1  = 120 을 구하는 문제이다. 

따라서 재귀 함수로 문제를 푼다 하면 n이 1이 아닐 때 까지 n * DFS(n-1) 을 하면서 곱해주면 되고, 0이 되기전 n 이 1이 되면 1을 리턴하고 재귀 함수는 종료된다. 

 

DFS(5) = 5 * DFS(4) 

                      4 * DFS(3) 

                             3 * DFS(2)

                                   2 * DFS(1) 

                                          1 

-> 이렇게 진행되고, 이제 계산할 때는 1 * 2 * 3 * 4 * 5 로 차례대로 스택에서 꺼내서 계산해주고, 마지막 값 120 을 리턴한다.