자바 팩토리얼 코드 재귀/메모이제이션 기법

04 March 2020 - 2 mins read time
Tags: 자바 손코딩

팩토리얼

팩토리얼은 1 부터 자기 자신까지의 수의 곱을 의미한다. 연산 기호로는 숫자뒤에 !를 붙여서. 예외적으로 0! 와 1! 는 둘다 1을 의미한다. 3! = 6, 4! = 24

팩토리얼 코드 버전 1 - 재귀

재귀를 활용한다면 코드를 짧고 간결하게 팩토리얼 로직을 구현할 수 있다.

int n = 10
fact(n)

int fact(int n) {
  if(n == 0 || n == 1){ 
    return 1
  } else {
    return n * fact(n-1)
  }
}

재귀로 표현하면 간결하고 쉽게 작성할 수 있지만 큰 단점이 존재한다. 수가 커졌을 경우 스택의 복귀 주소가 계속해서 쌓이다가 스택 오버플로우가 발생하여 코드가 멈춰버린다. 즉, 일정 숫자 이상의 크기는 재귀를 활용하여 팩토리얼 구현하는 것은 위험할 수 있다.

팩토리얼 코드 버전 2 - 메모이제이션

재귀의 방식이 편하지만 메모이제이션 기법을 활용하여 팩토리얼 코드를 구현할 수 있다.

int n = 10
int [] fact = new int[n + 1]
fact[0] = 1 ; fact[1] = 1

for(int i=1 ; i<=10 ; i++) {
  fact[i] = i * fact[i-1]
}

배열을 활용하여 이전의 팩토리얼 계산을 저장함. fact[2] = 2 * fact[1]이고 fact[3] = 3 * fact[2] 이런식으로 저장된 값을 활용하기에 계속해서 활용할 수 있다. 숫자가 늘어나도 배열의 사이즈를 크게 또는 타입형만 바꿔주면 되므로 스택 오버플로우의 문제를 걱정할 필요가 없다.

int n = 10
int [] fact = new int[n + 1]
if(fact[n] == 0 ) factorial(fact)
print(fact[n])

factorial(int [] fact) {
  fact[0] = 1 ; fact[1] = 1

  for(int i=1 ; i<=10 ; i++) {
    fact[i] = i * fact[i-1]
  }
}