[javascript] 재귀 호출 (Recursion)

재귀 호출 (Recursion)

• 정의 :  함수 안에서 자기 자신을 다시 호출하는 것을 의미
• 사용 상황 : 문제가 자기 자신을 포함한 형태일 때
  → 예: 트리 구조 탐색, 디렉토리 구조, 수학적 계산(피보나치, 팩토리얼 등)
  

재귀 함수의 호출 핵심

• 종료 조건 (Base case)  : 종료 조건이 없다면, 함수는 무한히 자기 자신을 호출하다가
         ❗️"Maximum call stack size exceeded" 오류가 발생 (스택 오버플로우)
• 자기 자신 호출 (Recursive call) : 문제를 더 작은 문제로 줄여 다시 호출

재귀 함수 구조의 기본

function 함수명(매개변수) {
  if (종료 조건) {
    return 결과;
  }
  return 함수명(다음 값); // 자기 자신을 다시 호출
}

재귀 함수 활용 예

// ex) 카운트 다운
function countdown(n) {
  if (n <= 0) {
    console.log('end');
    return;
  }
  console.log(n);
  countdown(n - 1); //  // 자신을 다시 호출함!
}
countdown(3); // ⇒ 3 2 1 end

// ex) 팩토리얼
function factorial(n) {
	/*
	// 재귀 함수의 종료 조건

	팩토리얼에서 0! = 1 이라고 수학적으로 정의되어 있기 때문에,
  만약 n이 0이면 더 이상 계산하지 않고 1을 리턴

	*/
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(3));
/* 실행 흐름
// ⇒ factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * (1 * factorial(0)))
= 3 * (2 * (1 * 1))   ← (바로 여기서 종료조건에서 리턴한 1을 사용
*/