[C언어/C++] 팩토리얼 재귀, 반복문 구하기 (factorial 함수)

안녕하세요. BlockDMask 입니다.

오늘은 재귀와 반복문을 이용한 팩토리얼(factorial) 함수를 구현해 볼것입니다.

<목차>

1. 팩토리얼이란? (factorial?)

2. 반복문을 이용한 팩토리얼 (for-loop factorial)

3. 재귀함수를 이용한 팩토리얼 (recursive factorial)

1. 팩토리얼(factorial) 이란?

▼ 팩토리얼 (n!)

어떤 양의 정수 n 이 있을때, 1에서부터 n까지의 자연수를 모두 곱한 값을 팩토리얼 이라고 합니다. (n 양수)

팩토리얼은 n! 라고 표현을 하죠. 식으로 나타낸다면 아래와 같습니다.

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

▼ 예를들어 팩토리얼 5을 구하라고 하면

5! = 5*(5-1)*(5-2)*(5-3)*(5-4) 가 되어서.

5! = 5*4*3*2*1 = 120 이 나오겠죠?

그렇다면, 영의 팩토리얼은 무엇일까요?

0! = 1

위에서 보시는것과 같이 0의 팩토리얼은 1입니다.

아래 예시가 C++로 되어있는것 처럼 보이지만, C언어를 하시는 분들도 무조건 이해할 수 있습니다.

제가 사용한 C++문법은 출력할때 밖에 없거든요.

2. 반복문을 이용한 팩토리얼

//[C/C++] factorial example1
//BlockDMask
#include<iostream>
using namespace std;
 
int factorial(int num)
{
    int result = 1;
    //for(int i = num; i>0; --i)
    for (int i = 1; i <= num; ++i)
    {
        result = result * i;
    }
    return result;
}
 
int main(void)
{
    int num = 5;
    int result = 0;
 
    //factorial for loop
    result = factorial(num);
 
    //print
    cout << "factorial " << num << "! : " << result << endl;
    system("pause");
    return 0;
}

▲ 반복문을 이용한 팩토리얼 예제

for문은 1부터 n까지 순회하나, n부터 1까지 순회하나 같기 때문에, 각자 입맞에 맞게 작성하면 됩니다.

i가 순회하면서 1 * 2 * 3 * 4 . . . . num 까지 곱한 수를 반환하겠죠?

3. 재귀를 이용한 팩토리얼

//[C/C++] factorial example2 (recursive)
//BlockDMask
#include<iostream>
using namespace std;
 
int factorial(int num)
{
    if (num <= 1) return 1;
 
    return num * factorial(num - 1);
}
 
int main(void)
{
    int num = 5;
    int result = 0;
 
    //factorial recursive
    result = factorial(num);
 
    //print
    cout << "factorial " << num << "! : " << result << endl;
    system("pause");
    return 0;
}

▲ 재귀를 이용한 팩토리얼 예제

재귀함수가 성립하려면 종료조건이 무조건 존재해야합니다. 그렇지 않으면 무한루프 무한호출에 빠지기 때문입니다.

예제의 재귀함수를 천천히 살펴보면, 종료조건이 if(num <= 1) return 1; 이 존재하죠?

그리고 return num * factorial(num - 1); 이렇게 또 자기 자신을 부릅니다. 하지만, 매개변수를 (num - 1)을 넣었죠?

천천히 살펴보면

맨처음 우리는 

factorial(5) 를 불렀습니다.

그리고 5는 1이 아니기 때문에 첫번째 if(num <= 1)는 통과하겠죠?

그리고나서 return 5 * factorial(4); 를 불러줍니다. 리턴을 할때 함수가 또 호출이 되었기 때문에 아직 반환이 되지 않고, 스택에 머믈러 있습니다. 

factorial(4)가 불리면 위와 동일한 방식으로 -> return 4 * factorial(3);

factorial(3)가 불리면 위와 동일한 방식으로 -> return 3 * factorial(2);

factorial(2)가 불리면 위와 동일한 방식으로 -> return 2 * factorial(1);

factorial(1)이 불리면, 이제 첫번째 if문인 if(num <= 1)에 걸려서 return 1 을 하게 됩니다.

이제까지 계산되지 않는걸 거꾸로 올라가겠죠? 계산되지 않은식은 아래와 같습니다.

factorial(5) = 5 * factorial(4);

factorial(5) = 5 * 4 * factorial(3);

factorial(5) = 5 * 4 * 3 * factorial(2);

factorial(5) = 5 * 4 * 3 * 2 * factorial(1);

이런방식으로 치환이 된거겠죠? factorial(1) = 1 이 종료조건이기 때문에 이 호출은 끝이 나게 되고.

함수가 아래에서부터 하나씩 하나씩 종료가 됩니다.

factorial(1)          = 1  을 반환하면서 종료

factorial(2) = 2 * 1  = 2  를 반환하면서 종료

factorial(3) = 3 * 2  = 6  을 반환하면서 종료

factorial(4) = 4 * 6  = 24 를 반환하면서 종료

factorial(5) = 5 * 24 = 120 을 반환하면서 완전 종료.

이런 방식으로 불리게 됩니다.

재귀함수는 함수자체가 있어보이고, 간결해 보이지만 값이 점점 커질수록(더많이 함수가 불릴수록) 비효율적이 됩니다.

재귀함수는 위에서 본것처럼 factorial(5)함수안에서 factorial(4)함수를 부르게 되면 2 함수가 끝나기 전까지는 A1 함수는 끝나지 않고 기다리게 됩니다. factorial(100)이라고 하게 되면, factorial(100) -> factorial(99) -> factorial(98) -> ... ... -> factorial(1) 까지 가게 되기 때문에 컴퓨터에 부하를 줄 수 밖에 없습니다.

감사합니다. 이해가 안가는 부분이 있으면 주저하지 말고 댓글 남겨주세요.!

또오세요~