재귀함수

재귀함수란?

한 함수가 자기 자신을 호출하는 형태

 

재귀호출은 알고리즘을 구현할 때 매우 유용합니다. 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다. 

스택(Stack)

재귀 호출을 이해하기 위해서 스택이라는 자료구조를 먼저 알아야 합니다. 컴퓨터가 호출 스택으로 함수를 실행하기 때문입니다. 

 

 

//Iterative code
function factorial (n) {
  var result = 1;
  for (var i = n; i >= 1; i--) {
    result *= i;
  }
  return result;
}

재귀 함수로 바꾸면 다음과 같습니다.

//recursive code
function factorial (n) {
  return n * factorial(n - 1);
}

//Uncaught RangeError: Maximum call stack size exceeded. 최대 호출 스택 사이즈가 초과

재귀 함수를 작성하여 호출하면 함수는 자기 자신을 계속해서 호출하며 실행합니다. 특정조건이 되었을때 재귀호출을 중단시키는 조건문장이 필요한데 이를 Base case 또는 Termination case라고 합니다.

function fac (n) {
  if(n === 1) {    //Base case
    return 1;
  }
  return n * fac(n - 1);
}

factiorial(5)
// 5 * fac(4)
// 5 * 4 * fac(3)
// 5 * 4 * 3 * fac(2)
// 5 * 4 * 3 * 2 * fac(1)
// 5 * 4 * 3 * 2 * 1 (fac(1) === 1) - Base case
// 120