함수의 재귀적 호출의 이해

재귀함수의 기본적인 이해

재귀함수란 다음과 같이 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.

void Recursive(void){
    printf("Recursive all! \n");
    Recursive();
}

이 형태의 함수 호출을 우리는 이렇게 이해할 것이다.

위의 그림이 혹시 이해되지 않을 경우 함수가 호출되면 함수의 복사본이 실행되는 구조로 이해해보길 바란다.

위 그림은 복사본이 복사본을 만들고, 또 그 복사본이 다른 복사본을 만들면서 실행되는 구조이다.

위의 Recursive함수는 탈출 조건이 없기에 무한 루프를 돌게 된다. 무한루프를 방지하기 위해 우리는 아래 코드와 같이 탈출 조건이라는 것을 추가해야 한다. 

#include<stdio.h>
 
void Recursive(int num) {
    if (num <= 0)
        return 0;
    printf("Recursive call! %d\n", num);
    Recursive(num - 1);
}
 
int main() {
    Recursive(3);
    return 0;
}

위 예제는 숫자가 0이하인 경우 함수가 종료되도록 해 놓았다.

그리고 num이 0이 되는 순간 '재귀의 탈출조건'이 성립되어 함수가 반환하기 시작한다.

재귀함수의 디자인 사례

재귀함수를 사용함으로써 문제를 단순화 시킬 수 있고, 재귀적인 수학적 수식을 그대로 옮길 수 있다. 

이러한 재귀함수의 특징을 팩토리얼(factorial) 값을 반환하는 함수를 재귀적으로 구현해 보겠다.

팩토리얼의 수식은 다음과 같다.

n! = n x (n-1) x (n-2) x (n-3) x ... x 2 x 1

위 수식을 코드로 옮겨보면

if (n == 0)
        return 1;
    else
        return n * Factorial(n - 1);

이렇게 쓸 수 있다. 

이번에는 팩토리얼 예제를 실행해보면서 실제로 값을 정확히 계산하는지 해보도록 하자

#include<stdio.h>
 
int Factorial(int n) {
    if (n == 0)
        return 1;
    else
        return n * Factorial(n - 1);
}
 
int main() {
    printf("1! == %d\n", Factorial(1));
    printf("3! == %d\n", Factorial(3));
    printf("6! == %d\n", Factorial(6));
}

--------------------------------------------------------

이 글은 <윤성우의 열혈 자료구조>를 공부하며 정리한 글입니다.