[백준 알고리즘] 10872 팩토리얼

 

 재귀 

: 원래의 자리로 되돌아가거나 되돌아옴

다시 자신의 함수를 호출하는 것을 재귀 함수라고 생각하면 쉽다.

 

재귀 함수를 작성할 때 중요한 것이 2가지가 있다.

1. base case를 만들 것

2. 스택이 줄어들어야 할 것

 

 

문제:    

https://www.acmicpc.net/problem/10872

10872번: 팩토리얼

풀이방법:    

"재귀" : 원래의 자리로 되돌아가거나 되돌아옴

다시 자신의 함수를 호출하는 것을 재귀 함수라고 생각하면 쉽다.

 

재귀 함수를 작성할 때 중요한 것이 2가지가 있다.

int factorial(int n){
    if(n < 1){
        return 1;
    }else{
        return n * factorial(n-1);
    }
}

1. base case를 만들 것

if(n < 1){
        return 1;

}

--> 프로그램이 끝이 나야하니까 계속적인 호출을 무한 반복을 해서는 안된다. 호출의 끝을 만들어줘야 한다 !

 

2. 스택이 줄어들어야 할 것

else{
        return n * factorial(n-1);
    }

--> 만약 return n * factorial(n); 이라고 코드를 작성했다고 하자. 그럴 경우에는 factorial(n)이 또 다시 factorial(n)를 호출하고 다시 factorial(n)을 호출하는 과정이 이루어진다. 이럴 경우 스택이 계속 쌓여서 에러가 발생하게 될 것이다. 따라서 factorial(n-1) n을 1씩 줄여가면서 base case에서 작성했던 것처럼 factorial(0)까지만 반복을 해야한다.

 

작성한 코드는 다음과 같다.

#include <iostream>
using namespace std;

int factorial(int n){
    if(n < 1){
        return 1;
    }else{
        return n * factorial(n-1);
    }
}

int main() {
    int n;
    int factorial_answer;
    cin >> n;
    factorial_answer = factorial(n);
    cout << factorial_answer <<"\n";
    return 0;
}

성공한 사진!