재귀함수, 팩토리얼 (factorial)

박영준·2023년 5월 10일

Java

목록 보기

72/112

1. 재귀함수

1) 정의

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 문제를 해결하는 방법
→ 스택(Stack)이라고 생각할 수 있다.
→ 함수가 콜 되면서 최근에 자신을 부른 원래 함수가 스택에 차곡차곡 쌓이게 됨.
처음 불려진 함수에서(스택 맨 밑에있는 메소드) return 되는 값이 최종 return 값이 된다.

2) 필요성

동적프로그램이나 병합정렬, 그래프탐색알고리즘 등의 특정한 부분의 개발에 유리하다.
가독성이 높다.
변수의 사용을 줄여준다.
- mutable state(변경 가능한 상태)를 제거해줌으로써 프로그램의 오류를 줄일 수 있다

단점
1. (For문에 비해) 속도 ↓
2. (For문에 비해) 메모리 낭비 ↑

2. 팩토리얼

1) 정의

3! = 3 * 2 * 1 = 6

4! = 4 * 3 *  2 * 1 = 24

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

팩토리얼은 재귀함수 中 하나.

2) 사용법

(1) For문을 이용한 Factorial 구하기

public class for_factorial {
    
    public static int factorial(int num) {
        System.out.print(num + "! = ");
        int sum = 1;
        for(int i = num; i>=1; i--) {
            sum *= i; // 반복문을 통해 i값의 곱을 sum에 결과값 저장
            if(i == 1) {
                System.out.print(i + " = ");
            }else {
                System.out.print(i +" x ");
            }
            
        }
        return sum;
    }
    
    public static void main(String[] args) {
        System.out.println(factorial(5));
    }
}

(2) 재귀함수를 이용하여 Factorial 구하기

public class Factorial {
    // 재귀함수로 factorial 구하기
    public static int factorial(int num) {
        if (num == 1)
            return 1;
        else
            System.out.println("factorial(" + num + ")"); //몇번 호출했는지 확인해보죠
            return num * factorial(num - 1);
 
    }
 
    public static void main(String[] args) {
 
        System.out.println(factorial(5));
    }
}

(3)

public class Test {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int result = factorial(10);
        System.out.println(result);
    }
    
    public static int factorial (int num) {
        if (num == 1)
            return 1;
        
        return num * factorial ( num - 1 );
    }
}