재귀(Recursion)와 재귀 호출 - JavaScript

재귀

구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 것.

즉, 문제를 더 나뉘지 않을 정도로 쪼개서 하나하나 해결하는 것.

 

재귀가 사용되는 상황

1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

 

재귀 호출

문제를 푸는 실행과정 도중에 자기 자신을 호출하는 것

 

 

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

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

 

 

 

 

*재귀는 알고리즘 문제의 많은 부분을 차지하며 기업의 알고리즘 테스트에도 활용되기 때문에 잘 알아놓아야 한다.