Tail Recursion
-
꼬리 재귀 (Tail Recursion)Study/자료구조,알고리즘 2022. 11. 3. 17:19
1. 꼬리 재귀 재귀 호출이 끝나면 아무것도 하지 않고 리턴하는 방법 컴파일러 최적화에 의해 재귀 호출이 깊어져도 스택 프레임이 쌓이지 않고 재사용하기 때문에 빨라진다. 2. 예시 int Factorial(int n) { if (n == 1) return 1; return n * Factorial(n - 1); } int FactorialTail(int n, int acc = 1) { if (n == 1) return acc; return FactorialTail(n - 1, n * acc); } 팩토리얼을 구하는 함수를 재귀방식, 꼬리 재귀 방식으로 작성해 보았다. 위 함수는 return statement에서 n * Factorial(n-1) 에 의해 재귀 호출을 빠져나가는 과정에서 * 연산을 해 주어..