[Algorithm] 팩토리얼 구하기(fatorial)

이전글참고

피보나치 수열이란?

1. 팩토리얼이란?

• 1 * 2 * 3 * 4 * 5 * 6, ...
• 팩토리얼은 다음과 같이 정의됩니다.

• f(n) = 1 * 2 * 3 * ... n
  5! = 1 * 2 * 3 * 4 * 5 = 120

2. Java로 팩토리얼을 구현해보세요

1) 첫번째 방법은 재귀로 구현해보겠습니다.

public class Main {

  public static int count = 0;

  public static void main(String args[]) {
    int n = 5;
    System.out.println(factorial(n));
    System.out.println("메서드 실행 횟수:"+count);
  }

  public static int factorial(int n) {
    count++;
    if(n == 1){
      return n;
    }
    return n * factorial(n-1);
  }
}

output > 120
output > 메서드 실행 횟수:5

• 시간복잡도 O(n)
• 공간복잡도 O(n) 이지만 Java8 컴파일러 레벨에선 TCO를 지원하지 않습니다.
  바로 꼬리 재귀를 이용하여 문제를 해결 하였습니다. (count++ 하는 부분에 break;를 걸어놓고 디버깅 해보면 꼬리 재귀가 되는걸 눈으로 볼 수 있습니다.)

2) 반복문으로 구현해보겠습니다.

public class Main {

  public static int count = 0;

  public static void main(String args[]) {
    int n = 5;

    System.out.println(fibonacci(n));
    System.out.println("메소드 실행횟수:" + count);
  }

  public static int fibonacci(int n) {
    count++;
    int result = 1;
    for(int i = 1 ; i <= n ; i ++){
      result = result * i;
    }
    return result;
  }
}

output > 120
output > 메서드 실행 횟수:1

• 시간복잡도 O(n)
• 공간복잡도 O(1)

2. 마무리

이전 포스팅에 피보나치 수열을 정확히 이해하고 이 문제를 풀어보니 접근하는 방향이 쉽게 잡혀서 좋았습니다.