특정 조건이 충족될 때까지 반복적으로 자신을 호출하는 알고리즘 유형입니다. 문제를 더 작은 하위 문제로 나누고 이러한 하위 문제를 재귀적으로 해결하여 문제를 해결하는 기술입니다. 보통 숫자 N의 계승(factorial)을 찾을 때 사용됩니다.

N! = N * (N-1)! if (N > 1)
N! = 1 if (N = 1)

• 이 재귀 정의는 N이 1에 도달할 때까지 함수가 입력 N-1로 자신을 호출하는 재귀 함수에서 구현될 수 있습니다.

재귀 알고리즘은 무한루프에 빠질 수 있으므로 반드시 종료 조건이 있어야 합니다. 보통 입력의 크기를 줄이면서 일정값에 도달했을 때 종료되도록 구현합니다.

구현방법

function sum(n) {
  if (n === 1) {
    return 1;
  }
  return n + sum(n - 1);
}

console.log(sum(10)); // 55

재귀 알고리즘은 대표적으로 퀵 정렬, 병합 정렬, 이진 탐색 등이 있습니다.