Search
Duplicate
🐈‍⬛

[C] 재귀함수와 꼬리 재귀함수

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
C
태그
Scrap
8 more properties

스택 프레임(Stack Frame)

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

재귀 (Recursion)

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

장점

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

단점

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

꼬리 재귀 (Tail Recursion)

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

장점

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

단점

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

참고