[C] Recursive Problem

이번 학기 데이터 구조 수업을 듣고 있다.

중간고사를 굉장히 잘 봤다고 생각했는데 전혀 아니었다.

알고보니 15점 짜리 한 문제를 0점 맞아버렸는데...

완전히 알고 있다고 생각했던 Recursive Problem 문제였다. 

아래의 코드의 Time complexity를 구하는 것이 문제

int f(int n){
    if(n<10){
        printf("O");
        return n+3;
    }else{
        return f(n-1)+f(n-1);
    }

문제를 보자마자 고심에 빠진 것이

"아... 15점 짜리 문제면 분명히 함정이 있을텐데.., f(n-1)+ f(n-1) 부분이 과연 2개의 함수를 호출하는 것인가"

에 대한 고심이었다... 결국 출제자의 의도를 파악하려던 나는 1개의 함수만 호출된다고 생각하고 답을 썼고

답은 2개의 함수가 호출되어 지수 형태의 TIme complexity를 가지는 것이었다.

오늘의 교훈 : 잘 모르면 처음 생각대로 가자