재귀함수를 사용할 경우, 비용이 생각보다 크다.

Untitled

  1. 메모리를 많이 차지하고 성능이 반복문에 비해 느리다.

→ 함수 호출 시 매개변수, 지역변수, 리턴값, 함수종료시 돌아가는 위치인 PC는 스택메모리에 저장되게 된다.

재귀함수를 쓰게 될 경우 함수를 반복적으로 호출하게 되므로 지속적으로 스택메모리에 함수 복귀주소가 쌓이게 되고, 자연스레 호출횟수가 많아지면 StackOverFlow Exception이 발생할 수 있다.

  1. 스택 프레임을 구성하고 해제하는 과정에서 ContextSwitching에 대한 비용이 크다.

Context Switching에 대한 비용은 상당하다. 재귀함수는 함수 호출과 복귀를 위한 ContextSwitching이 발생하게 된다. 물론 이런 비용을 최소화 위해 꼬리재귀(Tail Recursion) 방법을 사용할 수도 있다.

<aside> 💡 Tail Recursion에 대한 내용은 아래에 정리되어있다.

꼬리 재귀

</aside>

그럼에도 재귀함수를 사용하는 이유는 뭘까?

  1. 알고리즘 자체가 재귀적으로 표현하는 것이 자연스러울 때

Untitled

<aside> 💡 f(n) = f(n - 1) + f(n - 2)

</aside>

→ 실제로 실생활에 맞닫는 많은 알고리즘은 재귀적으로 표현되는 경우가 많다. 거의 모든 자료구조 역시 Recursive하게 정의되어있는 경우가 많으며 자연계의 대상체 역시 recursive한 경우가 많다. 당장 나뭇가지만 하여도 피보나치 수열을 따르게 되니.

성능적 실익을 떠나, 재귀적으로 구현하는 것 자체가 직관적이고 개발의 생산성을 높여주게 된다.

  1. 변수 사용을 줄여준다
int sum(const int x, const int acc) {
	if (x>100) return acc;
	else return sum(x + 1, x + acc);
}

변수 사용을 줄여준다는 뜻은 메모리적 측면이라기 보다는 MutableState를 제거하여 프로그램의 안정성을 높여준다는 의미이다. 가령, for문을 사용할 경우 함수가 끝날 때 까지 해당 변수에 대한 값을 지속적으로 동기화해주어야한다. 반면 재귀함수는 이런 MutableState를 최대한 회피할 수 있다.

또한, tail Recursion의 경우 최근의 컴파일러들은 for문과 같은 성능을 보장하는 경우가 대다수이기 때문에 이경우 Accumulator Pattern의 관점에서 보면 재귀함수가 훨씬 안정적이며, 성능적으로도 부족함이 없다고 할 수 있겠다.