재귀 함수(Recursive Function)

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

재귀 함수는 자기 자신을 호출하는 함수이다.

재귀로 문제 해결하기

• 문제를 가장 작은 단위까지 쪼갠다.
• 일반적으로 입력값을 기준으로 한다.
• 가장 작은 단위를 재귀의 기초(base case)라고 부르고, 나중에 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

재귀 함수의 일반적인 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

재귀를 이용하는 간단한 예시

• 5!(factorial) 구하기

// 5! = 5 x 4 x 3 x 2 x 1
// 5! = 5 x 4!
// 5! = 5 x 4 x 3!
// 5! = 5 x 4 x 3 x 2!
// 5! = 5 x 4 x 3 x 2 x 1!
function factorial(n) {
  if(n === 1) {
    return 1
  }
  
  return n * factorial(n-1)
}

factorial(5) // 120

• [1, 2, 3, 4, 5] 배열의 모든 요소의 합 구하기

// 15 = 5 + [4, 3, 2, 1]
// 15 = 5 + 4 + [3, 2, 1]
// 15 = 5 + 4 + 3 + [2, 1]
// 15 = 5 + 4 + 3 + 2 + [1]
// 15 = 5 + 4 + 3 + 2 + 1 + []
function sum(arr){
  if(arr.length === 0){ // 빈 배열의 길이는 0
    return 0
  }
  // shift는 배열의 맨처음 요소를 제거하고 제거한 요소를 리턴하는 메서드이고 기존의 배열을 변경함
  return arr.shift() + sum()
}

sum([1, 2, 3, 4, 5]) // 15
// sum([1, 2, 3, 4, 5]) = 1 + sum([2, 3, 4, 5])
// sum([2, 3, 4, 5]) = 2 + sum([3, 4, 5])
// sum([3, 4, 5]) = 3 + sum([4, 5])
// ...
//  sum([5]) = 5 + sum([])