재귀함수를 쓰는 이유

공부를 하다가 갑자기 무한 루프와 무한 재귀함수의 차이는 무엇인가에 대해서 고민을 해보게 되었습니다.

 

외국 사이트를 뒤져보다가 해답을 찾았는데 무한 재귀함수는 stack이라는 메모리 공간을 계속해서 이용하기 때문에 메모리의 제한이 있는한 stack overflow가 뜨면서 메모리가 펑! 하고 터져버린다고 합니다.

 

반복문의 경우엔 메모리를 이런식으로 사용하지 않아서 단지, 프로그램이 종료되지 않을 뿐이죠.

 

그렇다면 말이죠?

 

꼬리를 무는 질문이 생겼습니다.

 

왜 재귀함수를 쓸까요?

 

따지고보면 반복문보다 좋은 점도 없는데 말이죠. 심지어, 많은 사람들이 재귀함수가 반복문보다 느리다는 것을 이미 다 알고 있습니다.

 

그럼에도 불구하고 많은 사람들이 재귀함수를 흥미있게 다루고, 잘 사용하고 있는데, 그 이유를 한 번 알아보고자 합니다.

---

재귀 함수란 어느 함수가 자기 자신을 부르는 함수를 재귀함수라고 간단하게 말할 수 있습니다. 재귀 함수는 stack이라는 메모리 공간을 사용하는데, 반복적으로 자기 자신을 부르면 stack에 계속해서 자기 자신이 쌓여가기 때문에 성능이 좋지 않습니다.

 

그럼에도 불구하고 재귀함수를 쓰는 이유가 무엇일까요?

 

1. 알고리즘 자체가 재귀적인 표현이 자연스러운 경우에 재귀함수를 쓰는 것이 큰 도움이 됩니다.

 

재귀함수하면 항상 얘기나오는 피보나치 수열을 예로 들자면

 

1, 1, 2, 3, 5, 8 ...

 

첫 번째, 두 번째 숫자를 제외하면 n 번째 숫자는 n - 1, n - 2 번째 숫자를 합한 값입니다.

 

그렇다면 점화식을 세울 수 있겠죠. f(n) = f(n - 1) + f(n - 2)

 

위 점화식을 보시면, 결국 f(n)을 구하기 위해선 f(n - 1), f(n - 2)라는 자기자신의 함수를 인자만 바꾸고 다시 불러야 합니다. 이런 경우엔 재귀함수를 이용해서 간단히 구할 수 있겠죠. 물론 반복문도 가능하지만, 재귀적 표현이 자연스럽습니다.

 

많은 사람들이 위의 이유 때문에 재귀함수를 자주 사용을합니다.

 

2. 다른 이유는 '변수 사용'을 줄여줄 수 있습니다. (mutable state를 줄일 수 있습니다) 결과적으로 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워집니다. 즉, 사이드 이펙트(side effect)가 없습니다. (함수형 언어의 특징 중 하나이기도 합니다)

 

사실 이는 케바케로 직관적이지 않은 재귀 호출이 이해하기 어려울 수도 있지만, 프로그램이 복잡해지만 변수가 변하는 상황들을 가능한 피하는 것이 오류 없는 프로그램을 짜는 데에 중요한 사항이 됩니다.

 

int sum = 0;
for (int i = 0; i <= 100; i++) {
	sum += i;
}
printf("%d\n", sum);
////////////////////////////////////////////////////
int sum(const int x, const int acc) {
	if (x>100) return acc;
	else return sum(x + 1, x + acc);
}

printf("%d\n", sum(0, 0));

위의 두 코드를 비교해봅시다. 사실 0부터 100까지의 합을 구하는 코드인건 알 수 있습니다. 그런데 위엔 변수가 2개가 존재합니다. (sum, i) 하지만 밑의 코드엔 변수가 하나도 존재하지 않습니다. (x, acc가 변수로 보일 수 있지만, 실질적으론 x와 acc는 const로서 값 자체가 변화하진 않습니다)

 

위의 재귀함수를 tail recursion이라고 부르며, 위의 재귀함수 경우엔 stack overflow도 없으며, 반복문과 동일한 성능을 보장할 수 있습니다.

 

사실 직관적이지 않으며 헷갈릴 수 있습니다.

 

int sum(const int x) {
    if(x == 100) return x;
    else return x + sum(x + 1);
}

 

위의 경우에도 tail recursion으로 보이지만 x의 값을 계쏙해서 유지하게 됩니다. 즉, stack frame을 재사용할 수 없고 계속 쌓아가야만 합니다.

이를 피하기 위해 함수에 인자를 하나 더 추가해서 (보통 accumulator라고 부릅니다) tail call로 만든 것이 위에서 예로든 tail recursion 예입니다.

---

이렇게 알고보니 재밌지 않나요? 물론 저는 반복문을 쓸거 같지만, 이와 같은 차이점을 생각하고 코딩을 한다면 어디서 아는 척은 할 수 있을거 같습니다.

이상 재귀함수를 쓰는 이유였습니다. ^_^