꼬리재귀, Tail Recursion

Tail Recursion

일반적인 재귀함수는 특정 횟수 이상 호출 할 경우 Segment Fault를 출력하며 에러를 일으킨다. 하지만 꼬리재귀(Tail Recursion)은 이러한 문제점이 없다

프로그램을 실행하여 프로세스가 메모리에 올라갈 때에 메모리엔 여러 가지 공간들이 생성된다. 코드 데이터가 들어가는 코드 영역, 동적할당된 변수들이 저장되는 힙Heap) 영역, 지역변수들 혹은 함수의 매개변수들이 올라가는 스택 영역, 전역 변수들이 올라가는 bss, data 영역 등이 존재한다.

위에 말했듯이 재귀를 통해 지속적으로 함수를 호출할 경우 이 Stack 영역이 가득차게 되어 Segment Fault가 발생하여 프로그램이 종료된다.

조금 더 자세히 설명하자면, 만약 아래와 같은 코드를 실행할 경우

아래 그림과 같이 1, 2, 3, 4 순서대로 프로그램이 실행 되고 스택의 높은 주소 부터 낮은 주소까지 매개변수와 함수의 ret 등이 쌓이며 스택이 늘어난다.

이 때, 위와 같은 일반적인 코드가 아닌 재귀 함수를 호출할 경우 매개변수와 함수의 ret 함수 호출 횟수 만큼 쌓이게 되어 스택이 가득 차게 되고 에러가 일어난다.(Visual Studio에서 stack 사이즈는 기본 1M, 리눅스에선 8M)

호출한 함수를 종료하고 이후 해야 할 일이 없다면, 함수의 ret를 생성할 필요가 없게 된다. 즉 재귀적 함수를 원래 함수의 꼬리부분에서 호출 하는 경우를 꼬리 재귀(Tail Recursion)이라 한다.

꼬리재귀의 예를 들어, 아래와 같이 매개변수로 들어온 숫자부터 1까지 더하는 재귀함수가 있다면,

$ g++ sum.cpp -o sum
$ ./sum
10
55
100
5050
1000
500500
10000
50005000
100000
705082704
1000000
Segmentation fault: 11

10 ~ 1000의 숫자들은 제대로 결과를 출력하나, 100만 계산에서는 Segmentation fault가 일어났다.

이를 아래와 같이 꼬리 재귀 형식으로 바꿔 본다면,

$ g++ sum.cpp -o sum -O3
$ ./sum
10
55
100
5050
1000
500500
10000
50005000
100000
705082704
1000000
1784293664

100만 계산에서도 에러가 출력되지 않는다.

윈도우에서는 상관 없이 그냥 컴파일 하면 되지만, 리눅스에서는 -O3 옵션을 넣어 컴파일 해야 한다.

---

컴파일 최적화 옵션

위의 Tail Recursion을 리눅스에서 컴파일 시 -O3 옵션을 넣어서 컴파일 해야 한다고 했는데, 이 O3는 최적화 옵션이다. 기본적으로 gcc, g++을 그냥 컴파일 할 시 컴파일러에서 어떠한 최적화도 하지 않지만, -O{n} 옵션을 넣음으로써 원하는 최적화를 할 수 있다.

여러가지 옵션이 존재하지만, 기본적으로 -O0, -O1, -O2, -O3를 묶어서 사용한다.

-O0: 전혀 최적화를 하지 않는 default 옵션이다

-O1: 만들어지는 오브젝트 혹은 실행파일을 최대한 작게 하면서, 컴파일 시간이 오래걸리지 않는 선에서 최적화를 수행한다

-O2: 만들어지는 코드가 가능한 빠르게 수행되도록 하지만, 코드의 크기가 너무 커지지 않도록 하는 범위에서 최적화를 수행한다

-O3: 코드의 크기는 전혀 신경쓰지 않고, 오직 빠른 코드를 만들어 내기 위해 최적화를 수행한다

그러나, 생각해야 할 점은, -O3로 만들어 낸 실행 파일이 -O2로 만들어 낸 실행 파일 보다 빠르다는 보장은 없다. 왜냐하면, 보통 CPU가 기계어를 수행할 때, 일정한 분량만큼 먼저 CPU 내부의 cache에서 불러와 수행하는데, O3를 써서 만든 코드는 대개 크기가 커서, 이 cache에 들어갈 수 있는 명령의 양이 상대적으로 적어지기 때문에, 오히려 느려질 가능성도 있다*

Optimization	O0	O1	O2	O3
defer-pop	O	O	O	O
thread-jumps	O	O	O	O
branch-probabilities	O	O	O	O
cprop-registers	O	O	O	O
guess-branch-probability	O	O	O	O
omit-frame-pointer	O	O	O	O
merge-constants	O	O	O	O
loop-optimize	O	O	O	O
if-conversion	O	O	O	O
if-conversion2	O	O	O	O
align-loops	X	O	X	O
align-jumps	X	O	X	O
align-labels	X	O	X	O
align-functions	X	O	X	O
crossjumping	X	O	O	O
prefetch-loop-array	?	?	X	?
optimize-sibling-calls	X	O	O	O
cse-follow-jumps	X	O	O	O
cse-skip-blocks	X	O	O	O
gcse	X	O	O	O
gcse-lm	X	O	O	O
gcse-sm	X	O	O	O
gcse-las	X	O	O	O
expensive-optimizations	X	O	O	O
strength-reduce	X	O	O	O
return-cse-after-loop	X	O	O	O
return-loop-opt	X	O	O	O
caller-saves	X	O	O	O
force-mem	X	O	O	O
peephole2	X	O	O	O
regmove	X	O	O	O
strict-aliasing	X	O	O	O
delete-null-pointer-checks	X	O	O	O
reorder-blocks	X	O	O	O
reorder-functions	X	O	O	O
unit-at-a-time	X	O	?	O
schedule-insns	X	O	O	O
schedule-insns2	X	X	X	O
schedule-interblock	X	O	?	O
sched-spec	X	O	?	O
inline-registers	X	X	X	O
rename-registers	X	X	X	O
web	X	X	X	O
unswitch-loops	X	X	?	O

출처 : https://wiki.kldp.org/wiki.php/GccOptimizationOptions