알고리즘 대비(재귀-팩토리얼)

n!을 구하기
factorial 재귀함수를 만들어준다
재귀함수니까 종류조건을 만들어줘야함(필수)

종류 조건:
n ==0 일때 return 1;을 해줌
궁금했던 점 -> 왜 return 0;이 안될까 더이상 재귀호출도 없는데
재귀 호출 마지막에서 factorial(0)이 n==0조건에 참이 되니까 조건문이 실행됨
return 0을 해버리면 말 그대로 0이 리턴 되는데 그러면 n * n-1에서 맨 뒤에 0이 끼니까 결과값이 0으로 고정됨 그래서 곱해도 그대로인 1을 return해줌

재귀의 흐름과 복귀과정을 알아야함
f(3)이 호출되었을때로 가정
n factorial(n-1)이니까
3 factorial(2) 재귀호출됨
2 factorial(1) 재귀호출됨
1 factorial(0) 재귀호출됨
factorial(0) = 1 호출 끝
이제 복귀 해야함
factorial(0) = 1
1 (factorial(0) = 1)
2 (factorial(1) = 1)
3 * (factorial(2) = 2)
= 6

#include <stdio.h>

int factorial(int n){
    if(n == 0){
        return 1;
    }
    return n * factorial(n-1);
}

int main(void){
    int n;

    scanf("%d",&n);
    printf("%d\n",factorial(n));
}

제출했더니 틀렸다고함
20을 입력받았을때 음수 숫자가 출력됨
-> 오버플로우를 신경 안썼던 거였음
long long(long long int)로 바꿔줌

정답코드

#include <stdio.h>

long long factorial(int n){
    if(n == 0){
        return 1;
    }
    return n * factorial(n-1);
}

int main(void){
    int n;

    scanf("%d",&n);
    printf("%lld\n",factorial(n));
}