[C언어] 재귀함수란?

재귀

C언어는 함수가 자기 자신을 호출하는 것을 허용합니다. 이러한 것을 재귀(recursion)라 부릅니다. 재귀 함수를 호출하는 과정에서 재귀를 종료하는 조건식을 포함하지 않는다면 무한히 실행되는 불상사가 일어나기도 합니다.

 

재귀 함수의 예제

재귀 함수에 대해 알아보기 위해 예제(참고문헌: C기초 플러스)를 참고해보겠습니다.

#include <stdio.h>

void memoryRead(int n); //함수 선언

int main () {

    memoryRead(1);
    return 0;
}

void memoryRead(int n){
    printf("#1 %d 의 메모리 주소 %p \n",n,&n); //#1, %p를 지원하지 않을경우 %lu
    if(n<4){
        memoryRead(n+1);
    }
    printf("#2 %d 의 메모리 주소 %p \n",n,&n); //#2
}
//#1 1 의 메모리 주소 0x7ffeefbff5ac 
//#1 2 의 메모리 주소 0x7ffeefbff58c 
//#1 3 의 메모리 주소 0x7ffeefbff56c 
//#1 4 의 메모리 주소 0x7ffeefbff54c 
//#2 4 의 메모리 주소 0x7ffeefbff54c 
//#2 3 의 메모리 주소 0x7ffeefbff56c 
//#2 2 의 메모리 주소 0x7ffeefbff58c 
//#2 1 의 메모리 주소 0x7ffeefbff5ac 

 

main문은 memoryRead(1) 을 호출하고 함수 안에서 memoryRead(n+1) 로 자기 자신을 호출합니다. 또 호출된 함수가 실행되면 memoryRead((n+1) +1) 의 함수가 호출될 것입니다.

 

- memoryRead(1) 이 호출 //#1 1 의 메모리 주소 0x7ffeefbff5ac

- memoryRead(1) 안에서 memoryRead(2) 호출 //#1 2 의 메모리 주소 0x7ffeefbff58c

- memoryRead(2) 안에서 memoryRead(3) 호출 //#1 3 의 메모리 주소 0x7ffeefbff56c

- memoryRead(3) 안에서 memoryRead(4) 호출 //#1 4 의 메모리 주소 0x7ffeefbff54c

- n이 4이므로 if(n<4)의 조건문에 걸려 //#2가 호출된다 //#2 4 의 메모리 주소 0x7ffeefbff54c

- memoryRead(4)를 호출했던 memoryRead(3)의 #2가 호출 //#2 3 의 메모리 주소 0x7ffeefbff56c

- memoryRead(3)을 호출했던 memoryRead(2)의 #2가 호출 //#2 2 의 메모리 주소 0x7ffeefbff58c

- memoryRead(2)를 호출했던 memoryRead(1)의 #2가 호출 //#2 1 의 메모리 주소 0x7ffeefbff5ac

재귀 함수의 특징

첫 째, n의 값에 따른 메모리 주소가 다른 것으로 각 호출된 함수들은 자신만의 변수를 갖고 있습니다.(n 1과 2의 주소 값은 다릅니다.) 1부터 4로 다시 1로 돌아갔을 때는 1의 값은 같은 값을 유지하는 것 또한 확인할 수 있습니다.

둘째, 각 함수 호출은 return문에 의해 청산됩니다. 프로그램이 재귀의 마지막에 도달했을 때(여기서는 조건문), 다시 이전의 재귀로 복귀하게 됩니다.

셋째, 재귀 함수에서 재귀 함수 호출보다 앞에 있는 문장은 재귀 함수의 순서대로 실행됩니다. (#1 1,2,3,4)

넷째, 재귀 함수에서 재귀 함수 호출보다 뒤에 있는 문장은 재귀 함수의 순서의 반대로 실행됩니다. (#2 4,3,2,1)

다섯째, 재귀 함수의 각각 함수가 자신만의 변수를 갖더라도 코드는 중복되지 않습니다. 매 호출마다 새로운 변수를 만든다는 것을 제외하면 반복문 loop와 비슷합니다.

여섯째, 재귀 함수의  호출을 중단시킬 방법을 갖고 있어야 합니다.

 

꼬리 재귀

재귀 함수의 호출이 retrun문 바로 앞에 있는 것을 꼬리 재귀라고 부릅니다. 호출이 끝에서 이루어지고 루프처럼 동작하기 때문에 가장 간단한 재귀의 방법입니다. 계승을 구하는 팩토리얼(!) 예제로 꼬리 재귀를 알아보겠습니다.

#include <stdio.h>

long tailRecursionFact(int n); //함수 선언

int main () {
    int num = 5;
    printf("꼬리 재귀 팩토리얼: %ld\n",tailRecursionFact(num)); //꼬리 재귀로 팩토리얼 계산
    
    //loop로 팩토리얼 계산
    long value;
    for(value = 1; num > 1; num-- ){
        value *= num;
    }
    printf("for 루프 팩토리얼: %ld\n",value);
    return 0;
}

long tailRecursionFact(int n){
    long value;
    if(n > 0){
        value = n * tailRecursionFact(n-1);
    }
    else{
        value = 1;
    }
    return value;
}

//꼬리 재귀 팩토리얼: 120
//for 루프 팩토리얼: 120

 

- value = n * tailRecursionFact(n-1); //n이 5라면

- value = 5 * tailRecursionFact(4)

- tailRecursionFact(4) = 4 * tailRecursionFact(3)

- tailRecursionFact(3) = 3 * tailRecursionFact(2)

- tailRecursionFact(2) = 2 * tailRecursionFact(1)

- tailRecursionFact(1) = 1 * tailRecursionFact(0)//1

==>value = 5*4*3*2*1*1 = 120

 

for 루프와 동일한 결과를 내는 것을 볼 수 있습니다. 그럼 루프와 재귀 중 어느 것이 더 효율적일까요? 일반적으로 루프가 더 효율적인 코드입니다. 재귀는 각 재귀 호출이 자체의 변수를 갖기 때문에 재귀가 메모리를 더 많이 사용합니다.(스택) , 각 함수 호출에 시간이 걸리기 때문에 속도가 느립니다.