자료구조 : 재귀함수(Recursive Function)

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.

"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느날, 그 선인에게 한 선비가 찾아와서 물었어.

"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...

재귀함수와 관련된 재미있는 일화입니다. 이를 통해 한가지를 유추할 수 있죠. 위의 이야기는 "무한루프"에 빠지게 된다는 점입니다.

재귀함수에 대한 본격적인 설명을 시작하기 전에 제가 한가지 당부하고 싶은점은, 재귀함수를 만들때 빠져나가는 곳을 명확하게 정해놓지 않으면 재귀함수는 무한루프에 빠지게 됩니다. 마치 위의 이야기 처럼 말이죠.

그럼 본격적으로 재귀함수에 대한 설명을 시작하겠습니다.

재귀라는 단어를 국어사전에서는 "원래 자리로 되돌아 가거나 되돌아 옴" 이라고 하고 있습니다. 또한 익숙한 언어인 영어에서 재귀 대명사라는 말로 자기 자신을 가리키는 뜻으로 사용하기도 하죠. 이를 통하여 재귀함수는 자기 자신과 관련된 자기 자신에게 돌아오는 함수라고 유추해 볼 수 있겠습니다.

한마디로 정리하자면 재귀함수는 자기 자신을 호출하는 함수입니다. 그런데, 왜 써야 하는지, 어떤점이 좋은지 아직 감이 오지 않을 것입니다.

그래서 코드를 통해서 보여드리겠습니다.

int factorial(int n)
{
    if(n <= 1)
        return 1;
 
    return n * factorial(n-1);
}

임의의 숫자 n에 대한 팩토리얼을 구하는 코드입니다.

앞에서 이야기 했던대로 빠져나가는 곳을 제일 먼저 정의했습니다. n이 1과 같거나 작을때, 이를테면 1! 은 1이므로 1을 리턴하도록 하였습니다.

그리고 리턴문에서 재귀함수를 사용하여 n-1 을 파라미터로 넘겨 다시 함수가 실행되게 하였습니다.

처음부터, factorial(3); 이라고 해당 함수를 호출했을때, return 3 * factorial(2); 이렇게 변수가 대입되고, 팩토리얼 함수가 다시 실행되겠죠?

따라서,

factorial(3);
 
return 3 * factorial(2);
return 2 * factorial(1);
return 1;

이와같은 연산이 수행될 것입니다. factorial(1)은 1이므로 2*1 = 2, 2를 리턴, 3*2 = 6이므로 최종적으로 6을 리턴하여 팩토리얼을 수행할 수 있습니다.

이러한 재귀함수의 장점은, 직관적인 코딩이 가능하다는 점입니다. 위의 예시로 들었던 팩토리얼 같은 경우, 수학식으로 표현하면 n * (n-1) * (n-2) ... 인데, 이것을 직관적으로 n * (n-1) * (n-1-1) 과 같은식으로 똑같이 표현할 수 있다는 점입니다. 즉 쉽고, 빠르게 짤 수 있습니다.

그러나 재귀함수가 무조건 좋지는 않습니다. 함수가 자기자신을 재귀적으로 계속 호출하는 동안 메모리 스텍에는 리턴을 기다리는 재귀함수 자신이 쌓이게 됩니다. 따라서 큰 수를 n값으로 넣게 되면 스택 오버플로우가 발생하여, 프로그램이 터지게 되버립니다. 쉽게 말해서 성능이 떨어집니다.

때문에, 일반적으로 알고리즘을 코드로 옮길때 재귀함수를 이용하여 동작을 확인하고, 최적화 단계에서 for나 if를 이용한 루프문으로 바꾸는 식으로 많이 사용합니다.

int factorial(int num)
{
    for(int i = num - 1; i > 1; i--)
        num *= i;
 
    return num;
}

이렇게 루프문으로 바꾸는것이 성능 면에서는 훨씬 좋다고 할 수 있습니다.

지금까지 재귀함수에 대해서 알아보았습니다. 도움이 되었다면 좋아요와 광고를 한번씩 눌러주신다면 감사하겠습니다!