재귀함수

함수 내부에서 자기 자신의 함수를 반복해서 호출하는 것을 말한다.

재귀를 사용하는 시기

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

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

사실 모든 재귀 함수는 재귀 호출 없이 while / for loop으로 표현이 가능하다.
하지만 재귀를 사용 가능한 경우, 재귀를 사용한 코드가 대부분의 경우 더욱 간결하고 일부의 경우에는 이해하기도 쉽다.

재귀함수 코드 구현

function arrSum(arr) {
  // 재귀의 기초(base case)
  // 문제를 더 이상 쪼갤 수 없을 경우
  if(arr의 길이가 0인 경우) {
    return 0;
  }
  // recursive Case
  // 그렇지 않은 경우
  // head: 배열의 첫 요소
  // tail: 배열의 첫 요소만 제거된 배열
  return head + arrSum(tail);
}

아래는 일반적인 재귀 함수의 템플릿이다

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

예시

num을 입력받아 1부터 num까지 합 구하기

function sum(num) {
  if(num <= 1) {  // numdl 1일 때 재귀반복이 종료된다.
    return num;
  }
  return num + sum(num - 1); // 먼저 num을 더하고 -1 씩 하며 1이 될때까지 수를 더해준다.
}