재귀 알고리즘 팩토리얼 예제

 

목차

---

1. JAVA 코드를 통한 팩토리얼 예제

 

---

 

 1. JAVA 코드를 통한 팩토리얼 예제

 

소스는 다음과 같다.

1.  public static void main(String[] args) {
2.
3.     int no = 4;
4.     System.err.println("결과 : "+factorial(no));
5. }
6.
7. public static int factorial(int n){
8.     System.out.println("n : "+n);
9.
10.     if(n > 0){
11.         int recursiveResult = factorial(n - 1);
12.         int result = n * recursiveResult;
13.         System.out.println("factorial(" + n + ") = " + n + " * factorial(" + (n-1) + ") = " + result);
14.         return result;
15.     }else{
16.         return 1;
17.     }
18.
19. }

 

간단하게 4! 문제를 구하는 문제였는데 생각보다 개념이 잘 잡히지 않아 정리해본다.

실행 과정은 다음과 같다.

 

1. 우선 8번째 줄에서 4가 찍힌 뒤 if(4 > 0)을 타고 11번째 줄에서 다시 함수가 호출되어 8분째 줄로 올라간다.

2. 해당 과정을 반복하면 call stack은 아래와 같은 형태가 된다. 

 

3. 이후 n이 0이 되는 순간 return 1을 시작으로 factorial 함수가 종료되기 시작한다.
    이때 콜스택은 선입후출의 순서로 진행이 되므로 factorial(0)부터 아래의 순서로 종료가 되기 시작한다.

4. 이제 함수가 종료되었기 때문에 11번째 줄인 recursiveResult 변수에 값이 대입이 되며 아래의 코드들이 실행된다.

5. 모든 함수가 실행되어 콜스택이 비어지게 되었을 때 13번째을 통해 콘솔에 찍힌 값들은 아래와 같다.

 

- 최초 리턴값인 factorial(0) == 1 이므로 fatorial(1) ==  1 * 1 이 된다.

- factorial(2)는 2 * factorial(1)인데 factorial(1)은 위에서 1로 계산됨.

- 아래의 값들도 위의 결과값을 토대로 계산되어 나온다.

 

* 11, 12 번째 라인의 수식은 아래와 같다.

factorial(4)
            = 4 * factorial(3)
            = 4 * (3 * factorial(2))
            = 4 * (3 * (2 * factorial(1)))
            = 4 * (3 * (2 * 1))
            = 24

 

확실히 직접 콜스택을 디버그로 확인하며 구현을 해보니 이제 이해가 된다.

재귀 알고리즘 문제를 풀 때 처리 과정을 그리려고 하면 힘드니 재귀 조건과 인자만 신경 쓰면 된다는 글들을 많이 봤지만 기본적인 처리 과정은 이해하고 넘어가는 게 맞는 거 같았다.

꽤나 고전했지만 겨우 이해를 마치고 기록을 남긴다.