본문 바로가기
공부(~2016)/알고리즘

[Java] 팩토리얼

by soy; 2013. 5. 22.

팩토리얼


public class Factorial {
 
    public static int factorialByLoop(int n) {
        int sum = 1;
        for(int i=n; i>1; i--)
            sum = sum*i;
        return sum;
    }
    
    public static int factorialByRecursion(int n) {
        if(n==1)
            return 1;
        
        return n * factorialByRecursion(n-1);
    }
    
    public static void main(String[] args) {
        System.out.println( Factorial.factorialByRecursion(5) );
        System.out.println( Factorial.factorialByLoop(5) );
    }
}



재귀로 구현한 프로그램은 모두 비재귀적(루프 형태)으로 변경할 수 있다. 실제로 컴파일러는 재귀함수를 루프 형태로 변경하여 실행한다.

재귀를 쓰면 n이 클 때 스택오버플로가 발생할 수 있으므로 주의해야한다.

base case 체크에 신경쓰자

팩토리얼 함수를 한 번 호출한다면 중복 계산은 일어나지 않는다. 하지만 여러번 호출하는 경우라면 memoization을 이용할 수 있다.

댓글