함수가 자기 자신을 다시 호출해 문제를 푸는 방식. 같은 함수를 점점 작은 입력으로 부르다가 더 나눌 필요가 없는 지점(기저 조건, Base Case)에서 멈춘다.
두 가지 필수 조건
- 기저 조건: 재귀가 끝나는 조건
- 매번 다른 입력: 호출할 때마다 기저 조건에 가까워져야 한다
둘 중 하나가 빠지면 끝없이 호출되다가 스택 오버플로(Stack Overflow)가 난다. 결과를 return하지 않거나 엉뚱한 값을 돌려주는 것도 흔한 실수다. 호출이 쌓이는 곳이 콜 스택(Call Stack)이기 때문이다.
const sum = (arr: number[]): number => (arr.length === 0 ? 0 : arr[0] + sum(arr.slice(1)))두 가지 모양
- 헬퍼 메서드 재귀(Helper Method Recursion): 바깥 함수는 재귀가 아니고, 결과를 모을 변수를 둔 채 안쪽 헬퍼 함수가 재귀한다. 이해하기 쉽다
- 순수 재귀(Pure Recursion): 매번 새 값을 만들어 반환값으로만 결과를 쌓는다. 배열은
slice·스프레드·concat으로 복사해서 원본을 바꾸지 않는다. 위sum이 그 예다(다만slice가 매번 복사하므로 큰 배열엔 비효율적이다)
어디에 쓰나
트리와 그래프 순회(트리 순회, 깊이 우선 탐색 (DFS)), DOM 탐색, 중첩 객체 복사(얕은 복사와 깊은 복사), JSON 직렬화, 분할 정복 알고리즘. 같은 부분 문제를 반복 계산한다면 결과를 저장하는 동적 프로그래밍으로 넘어간다. 깊이가 아주 깊어질 수 있다면 명시적 스택을 쓰는 반복문으로 바꾸는 것이 안전하다.