[Algorithm 014] JS - factorial

Q. 재귀를 사용하여 팩토리얼(factorial)을 구하는 함수를 구현해주세요.

팩토리얼이란 1에서부터 n까지의 정수를 모두 곱한것을 말합니다.

1! = 1
2! = 1 * 2
5! = 1 * 2 * 3 * 4 * 5

 

 

A. 답

const factorial = n => {

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

factorial(3) // 6

if 를 적지 않았다가 RunJS가 뻗어버렸다.

• 재귀함수는 자신을 계속 호출하므로 이를 중단시키는 특정 조건문이 반드시 하나 이상 들어가야한다.
  이것을 Base case(=Termination case)라고 한다.
• 마지막에 1을 반환하는 이유 : 종료 값을 반환할 때 값에 지장을 주지 않기 위해 1을 곱한다. 

1*1 = 1
2*1 = 2
3*1 = 3

 

turn 01

factorial(3) ===  3 * factorial(3-1) = 3 * factorial(2)

 

turn 02

factorial(2) ===  2 * factorial(2-1) = 2 * factorial(1)

 

turn 03

factorial(1) ===  1 * factorial(1-1) = 1 * factorial(0)

 

factorial(0) === 1

 

자료 구조 중 stack의 LIFO로 실행된다고 한다. 그래서 3 * 2 * 1이 아닌 1 * 2 * 3으로 실행