스택 프레임(Stack Frame)

메모리의 스택(Stack) 영역은 함수 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역이다.

재귀 (Recursion)

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

장점

• 코드가 짧아져 가독성이 높아진다.

단점

• 스택의 최대 깊이가 $O(n)$ 이다.
• 잦은 점프로 인해 반복문(iteration)보다 속도가 느리다.
• 무한 재귀가 발생할 경우, 반복문과 달리 프로그램이 중지되지 않아 CPU 크래시가 발생한다.
• 연속 호출로 인해 최대 스택 크기 이상의 메모리가 스택에 쌓이면 스택오버플로우가 발생한다.

꼬리 재귀 (Tail Recursion)

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

장점

• 스택의 최대 깊이가 $O(1)$ 이다.

단점

• 컴파일러에서 꼬리 재귀함수(TCO; Tail Call Optimization)를 지원해야 사용이 가능하다.

참고

코딩교육 티씨피스쿨