[백준 문제풀이] 10872번 팩토리얼

10872번 팩토리얼 (Bronze 3)

문제

https://www.acmicpc.net/problem/10872

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

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다.

출력

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

재귀함수란?

재귀함수란 함수에서 스스로를 호출해서 명령을 수행하는 함수이다. 반복문을 사용하는 명령은 모두 재귀 함수를 통해 구현이 가능하고, 재귀함수를 반복문으로 만드는 것도 가능하다.

재귀함수를 만들 때는, 재귀 호출을 그만둘 수 있는 조건을 만들어야 무한 루프를 막을 수 있다.

재귀 함수는 단순히 명령을 반복하는 것이 아니라, 함수를 반복해서 호출하므로 메모리를 많이 차지하기 때문에 반복문에 비해 느리다.

그럼에도 재귀함수를 사용하는 이유는 변수를 만들 필요가 없으며, 반복문을 사용하지 않기 때문에 코드가 매우 간결해지기 때문이다.

다만 위에서 말한대로 단순한 반복문이 아니라 반복적으로 함수를 호출하기 때문에, 해당 함수에서 필요한 것들을 메모리에 저장하는 과정에서 스택 메모리가 커지고, stack overflow가 발생할 수 있다.

이러한 에러를 방지하기 위해 사용하는 방법이 ‘꼬리 재귀 최적화’ 이다.

꼬리 재귀는 재귀 함수의 호출 이후 바로 결과만 반환할 수 있도록 하는 방법이다. 이러한 것은 코드에서는 바로 볼 수 없고, 자바스크립트 언어에서 ‘꼬리 재귀 최적화’라는 기능을 지원해주기 때문이다. 이러한 이유로, 꼬리 재귀에서 return 값은 마지막(tail - 꼬리)부분에 있어야한다.

재귀 함수 예시

1
2
3
4
5
6

function factorial(n) {
  if (n === 1) {
    return total;
  }
  return n * factorial(n - 1);
}

꼬리 재귀 예시

1
2
3
4
5
6

function factorial(n, total = 1) {
  if (n === 1) {
    return total;
  }
  return factorial(n - 1, n * total);
}

출처: https://joooing.tistory.com/entry/재귀-→-꼬리-재귀-Tail-Recursion [joooing]

둘이 뭐가 다른 걸까?

위에서 설명된 일반 재귀는 값을 받으면, 그 값에 연산을 하고 다시 재귀 함수에 전달해줬다. 하지만 꼬리 재귀는 아무것도 하지 않고 인수로 total 값을 전달만 해준다. 결과 값에 아무 일도 하지 않고 다시 반환하기 때문에, 스택 오버플로우가 발생하지 않게 되는 방식이다.

콜스택과 스택 오버플로우, 꼬리재귀 최적화

자바스크립트는 단일 스레드 프로그래밍 언어이다. 이 말은 쉽게 말하자면, 자바스크립트라는 언어는 안에 들어있는 계산 요정님이 한 명에다가 멀티태스킹은 할 줄 모른다라는 것이다.

그렇기 때문에 콜스택이라는 실행 대기열을 만들고, 하나씩 대기열에서 명령을 꺼내서 처리해준다.

근데 이 요정님께도 역량과 나름의 사정이 존재하기 때문에 우리가 요청할 수 있는 대기열의 최대 길이는 13939개 정도이다.

그래서 많은 양의 함수가 있을 때 요정님께

첫 번째로 값을 받으시구요. 두 번째로 이 값을 곱해서 세 번째로 아까 이 값 드렸던 위치로 전송 부탁드려요.

같이 여러 일로 내용을 나눠서 요청을 하게 되면, 요정님은 파업해버리신다. 이 파업선언이 일반 재귀에서 마주할 수 있는 Uncaught RangeError: Maximum call stack size exceeded이다.

그렇기 때문에 꼬리재귀를 사용해서 요정님이 할 일을 간단 명료하게 줄여주는 것이다. 꼬리재귀를 사용하게 되면

다음 함수 부르실 때, 곱해진 이 값좀 같이 넘겨주세요.

라는 간략화된 요청으로 말할 수 있게된다.

풀이

꼬리 재귀를 구현해서 풀었다. 재귀는 아직 너무 어렵다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const fs = require("fs");

const input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());

function factorial(n, total = 1) {
  if (n === 0 || n === 1) {
    return total;
  } else {
    return factorial(n - 1, n * total);
  }
}

const answer = factorial(input);

console.log(answer);