[코딩테스트] 재귀로 팩토리얼 구현하기

1. 문제

자연수 N을 입력하면, N! 값이 출력되도록 만드시오.

 

1) 팩토리얼

팩토리얼은 n이 자연수일 때, 1부터 n까지의 자연수의 곱을 의미한다.

n!으로 표시한다.

 

예를 들어, 5! = 5*4*3*2*1 = 120이다.

이는 5! = n*(n-1)*(n-2)... 이런 식으로 나타낼 수 있다. 

 

위 식을 활용하면 재귀함수를 통해 간단하게 팩토리얼을 구현할 수 있다. 

 

2. 풀이

function solution(n) {
    let answer;

    function DFS(n) {
        if (n === 1) return 1
        else return n * (DFS(n - 1));
    }

    answer = DFS(n);
    return answer
}

console.log(solution(5));

 

팩토리얼 만드는 방법은 간단하다.

주어진 숫자에서 1씩 빼면서 곱해주면 된다.

 

answer = DFS(5)가 처음에 호출되면, else 문에서 5*(DFS(5-1))을 호출한다.

그러면서 DFS(5)는 스택에 쌓이고 DFS(4)가 호출된다.

 

이때 return 값은 5*(DFS(5-1))가 된다.

즉, 함수 실행이 끝나지 않았으므로 밖으로 나가지 않고 다음 함수를 실행하게 된다.

 

DFS(4), DFS(3), DFS(2)를 거쳐서 DFS(1)이 되면, if문에 해당되므로 1을 리턴하게 된다. 

이렇게 DFS(1)이 끝나면, 스택에서 빠져나가고 DFS(2)가 마저 실행된다.

 

DFS(1)의 return 값은 1이므로 2*(DFS(1))은 2*1이 되고 DFS(2)도 스택에서 빠져나간다.

그럼 스택에 쌓여있던 DFS(3)이 실행되고, DFS(2)의 return 값은 2*1이므로 3*(DFS(2))는 3*2*1이 된다.

 

위 과정을 반복해서 DFS(5)까지 끝나면 5*4*3*2*1이 되고, 해당 값이 answer에 들어가며 120을 리턴하게 된다.