재귀

재귀함수의 사용 이유

#include <iostream>

using namespace std;

//일반적인 재귀함수
int factorial(int input) {

	if (input == 1) {
		return 1;
	}

	return input * factorial(input - 1);
}

int main() {

	cout << factorial(5) << endl;

}

재귀 함수는 자기가 자기 자신을 부르는 구조이다. 위 코드는 재귀 함수의 사용 예시를 들때 단골 손님으로 등장하는 facotorial 구현이다. 구현 로직은 정말 간단한데 n의 factorial을 구하고 싶으면 n * {(n-1)의 factorial}을 계산하는 꼴이다. 수학에서 점화식을 생각하면 편할 듯 하다.

이러한 깔끔하고 섹시한 재귀함수에도 단점이 있었으니 이는 스택을 너무 많이 활용해서 공간 복잡도 측면에서 않좋다는 사실이다. 위 코드에서 5!만 돌려도 함수 스택이 5개나 쌓였다가 (input==1)의 종료 조건을 만나고 하나씩 줄어들게 된다.

꼬리 재귀

이러한 재귀 함수의 단점을 보안하기 위해서 꼬리 재귀(Tail Recursion)하는 것이 등장했다.

꼬리 재귀를 사용하기 위해서는 다음 2가지 조건을 만족해야 한다.

• 재귀 함수를 꼬리 재귀 방식으로 구현할 것
• 컴파일러가 꼬리 재귀 최적화를 지원할 것

팩토리얼의 코드를 꼬리 재귀 함수로 구현한 코드를 만나보자.

Compiler 버전

#include <iostream>
using namespace std;

int main(){
	// compiler version 체크하는 코드
	cout << __cplusplus << endl;
}

Output >> 199711...??

int와 longlong으로도 표시못하는 값을 찍어보기 위해 __int128_t라는 변수형을 선언하려고 했더니 compiler 버전이 오래되어서 자료타입을 인식하지 못했다! __cpluscplus로 찍어보니 무려 1997년도... 바로 컴파일러 버전을 업그레이드 했다.

Reference

링크