재귀함수 시간초과

백준 11050

재귀함수 구현 방식에 따른 시간차이

한 단계 낮은 문제가 해결되고 이를 바탕으로 답을 얻을 수 있는 경우 재귀적 문제 해결방식을 고려해보아야 한다.

재귀함수 구현 시 주의사항

: 재귀함수를 사용하여 코드를 구현하면 스택에 함수가 쌓인 후 값이 차근차근 반환되므로 오버플로우가 발생할 수 있다. (함수호출반환에 오버플로우가 발생하거나 스택 오버플로우가 발생할 수 있다.)

따라서 아래의 코드에 시간초과가 발생하였다.

 

시간초과 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int factorial(int n) {

        if (n == 1) return 1;

        return n * factorial(n - 1);

}

int main(void) {

        int n, k;

        int result = 1;

        scanf("%d %d", &n, &k);

 

        printf("%d", factorial(n) / factorial(n - k) * factorial(k));

}

 

정답 코드

- 간단하게 for문으로 구현하였다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int factorial(int n) {

        int result = 1;

        for (int i = 1; i <= n; i++) {

                result = result * i;

        }

        return result;

}

int main(void) {

        int n,k;

        int result = 1;

        scanf("%d %d", &n,&k);

 

        printf("%d", factorial(n) / (factorial(n-k)*factorial(k)));

}