팩토리얼 함수 코딩, 알고리즘 ,Factorial Algorithm (재귀함수)

---

앞에서는 반복함수로 팩토리얼 알고리즘을 구현하였는데 

이번에는 재귀함수를 사용하여 팩토리얼을 구해보도록 하겠습니다.

그림이 이해가 되셨으면 좋겠네요

재귀함수, 재귀호출 이라고 하며 여기서 재귀는

자기 자신을 포함하고 다시 자기 자신을 사용한다 

이런 느낌을 재귀적이라고 합니다. 

 

무슨말인지 모르시겠다면 그게 맞는겁니다.

 

나는 나고 나라는건 나야 

재귀적으로 자신을 말할때 저렇게 말할 수 있게됩니다.

 

무슨말인지 모르시겠다면 그게 맞는겁니다.

 

즉 자기 자신을 포함하는 것이라고 생각하시면 편할것 같습니다.

 

팩토리얼을 설명하는데 왜 재귀함수를 이야기하는지 모르시겠다구요?

여기서 팩토리얼의 공식을 조금 더 자세히 살펴보겠습니다.

 

이해를 돕기위해 n > 5 라고 가정할시

n! = n*(n-1)*(n-2)*(n-3)...........4*3*2*1 입니다.

(n-1)! = (n-1)*(n-2)*(n-3)...........4*3*2*1 

(n-2)! = (n-2)*(n-3)...........4*3*2*1 

(n-3)! = (n-3)...........4*3*2*1 

.

.

.

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

4! = 4*3*2*1 

3! = 3*2*1 

2! = 2*1 

1! = 1 입니다.

---

무언가 보이시나요? 얼른 코드만 보여드리면 되는데

왜이렇게 서론이 길까요?

 

여기서 팩토리얼 안에 팩토리얼이 존재한다는걸 알아채신분들이 있기를 바랍니다. ㅠㅠ

즉, n! 안에 (n-1)! 이 존재하며

(n-2)!안에서는 (n-3)!이 존재합니다.

 

그래서 팩토리얼 공식을 다시 정의하면

n! = n*(n-1)! 로 나타 낼 수 있게 되는 겁니다.

여기까지 재귀적 표현을 이해하셨으면 재귀함수 구현은 쉬워지게 됩니다.

 

앞서 반복함수로 표현한것과 달리 

함수 안에서 함수를 호출하면 되니까요

 

자바로 구현 했으며,

물론 다른 언어도 방식은 똑같습니다.

 

재귀함수를 사용하여 팩토리얼 코드 만들기

---

public static long factorial_R(int n) { // 반환값은 int형도 상관 없습니다.

    if (n == 1) { // 1! 일때의 경우를 따로 정의합니다. 
    return 1; 
    }

    else {
    return n*(factorial_R(n-1)); // 여기서 반환값에 우리가 정의한 factorial_R함수를 다시 호출합니다.

    반환값은 처음의 n값과 n에서 -1 된 factorial_R 함수의 반환 값의 곱이 되게 되며

     n! = n*(n-1)! 과 같은 표현이 되겠습니다.

    }
}

---

코드로 표현하면 반복함수를 사용하였을 때보다 많이 간단해지는걸 볼 수 있게됩니다.

단순하게 팩토리얼 알고리즘이 저거 구나 보다는

재귀적인 표현에 대해 이해를 하셨으면 합니다.

도움이 되셨으면 좋겠습니다. 땡큐