[자료구조] 재귀함수(Recursion) 개념과 구현, 재귀함수 vs for loop

재귀함수(Recursion)은 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법을 의미한다. Ex) 팩토리얼

재귀함수는 스택에 저장하고(push) 빼내는(pop) 형식을 생각하면 이해하기 편한데, 이를 c 코드로 정리하면 다으모가 같다.

 

void Rec(0){
    if (n<=0) return;
    printf("Rec(%d)\n", n));
    Rec(-1);
    printf("Rec(%d) done! \n", n));
}


void Rec(1){
    if (n<=0) return;
    printf("Rec(%d)\n", n));
    Rec(0);
    printf("Rec(%d) done! \n", n));
}

void Rec(2){
    if (n<=0) return;
    printf("Rec(%d)\n", n));
    Rec(1);
    printf("Rec(%d) done! \n", n));
}

 

재귀함수 n!는 n*(n-1)! 를 진행하는 것에 반해, for loop n!는 n부터 1까지 모든 수를 곱한다는 점에서 차이가 있다. 재귀의 경우에는 코드를 이해하는 데 비교적 간편한 대신, 실행시간이 길어질 수 있다는 단점이 있다.