[알고리즘] 재귀(Recursion)함수를 이해하고 팩토리얼 계산 구현

재귀함수의 기본적인 이해

재귀함수는 말 드대로 함수는 함수내에서 자기 자신을 다시 호출하는 함수를 의미한다.

#include <stdio.h>
 
void Recursive(void) {
    printf("Recursive call! \n");
    Recursive();
}
 
int main() {
    Recursive();
}

Recursive함수에서 Recursive()으로 자기 자신을 다시 호출한다. 실행결과는 "Recursive call" 이 계속 출력되는 무한 츠쿠요미에 걸리게 된다. 여기서 아 그렇구나 라고 이해하면 안된다. 원래는 Recursive 함수가 호출 될때 마다 계속해서 Recursive 함수의 복사본이 만들어져서 복사본이 실행되는 구조이다. 여기서 이해가 안될텐데 그림을 보자

그림은 복잡해 보이지만 실제로는 훨씬 이해하기 좋은 구조이다. 함수가 호출되면 해당 함수의 복사본을 만들어서 실행하는 구조이기 때문에 다음과 같은 논리적인 이해가 가능하다.

"Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행한다."

위 문장의 내용은 재귀적인 형태의 함수호출이 가능한 이유를 충분히 설명하고 있다. 그러나 나는 여기까지 읽어도 먼 소린지 잘 몰랐다. 

다음 예제는 재귀함수를 탈출하는 예제이다.

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

Recursive 함수에서 if문은 탈출조건이다. num값이 0이하인 경우 함수가 종료 되도록 정의되어 있다. 실행 과정을 생각해보자 Recursive(3) 이 호출되고 그 안에서 Recursive(2)가 호출되고 또 그안에서 또 Recursive(1)이 호출된다 마지막으로 Recursive(0)이면 함수를 호출한다. return이 일어나면 함수탈출은 Recursive(0)에서 일어난다 그럼 그 다음은 어디로 가는 것일까? 위에서 말한 복사본을 생각하면 된다 Recursive(0)은 복사본 Recursive(1) 함수에 있는 이라는 복사본에 리턴하고 수명을 다했다. 또 Recursive(2)는 Recursive(3)에 리턴하고 수명을 다하는 것이다 즉 실타래 처럼 서로 이어져 있는 것이고 그 return을 통해 실타래의 매듭을 하나씩 풀어 나간 것이다. 

정확하게는 리턴된 값은 재귀함수 호출문인 Recursive(num-1) 리턴된다. 그림을 보면서 다시 이해해 보자.

위 그림에서 보이듯이 재귀적으로 호출이 이뤄지고 있는 Recursive 함수에 0이 전달되면서 재귀의 탈출조건이 성립되어 함수가 반환하기 시작한다. 반환하는 과정이 실타래의 한 매듭이 풀려나가는 것이다. 이렇듯 재귀함수를 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한 일이다.

재귀함수의 대표적이고 기본적인 디자인 사례(팩토리얼)

재귀함수를 이용한 가장 기초적인 알고리즘을 팩토리얼 계산이다.  팩토리얼은 n! 이면 n * (n-1) * (n-2) ... 2 * 1 을 하는 계산 기법이다. 먼저 코드를 보자

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

n == 0 이 팩토리얼 함수의 탈출 조건이다. 즉 factorial(0) 실행부터 탈출한다는 뜻이다.  factorial 함수의 정의 과정은 앞으로 재귀함수를 구현하는데 있어서 중요한 모델이 된다. 코드만 이해하지말고 그 과정을 이해해보자 쉽게 되진 않을 것이다.

실제 그림처럼 과정이 이루어진다 먼저 factorial(3) 이 호출되고 그 다음 return 문에서 factorial(2)가 호출 그리고 factorial(2) return문에서 factorial(1)을 호출한다. 마지막으로 factorial(0)에서 return 1이 실행되고 반환하기 시작한다. 즉 매듭을 풀기 시작하는 것이다

연산 실행은 3*2*1 순으로 되는줄 알았지만 실제로 연산은 return 1 이 되고나서 1 * 1 부터 시작한다. 즉 실제 연산은 1*1 -> 2 * 1 -> 3 * 2 이런식으로 이루어 진것이다.

이제 자기가 한번 직접 그림 그려보면서 생각해보면 완벽히 이해할거라 생각한다.

윤성우, 『윤성우의 열혈 자료구조』, ORANGE MEDIA

그림출처 : m.blog.naver.com/PostList.nhn?blogId=nsj880424