1. 재귀

   1.1 재귀 개념을 이해할 수 있다.

   1.2 무한 loop에 빠지지 않도록 재귀를 이용할 수 있다.

   1.3 call stack이 넘친다는 것의 의미를 이해할 수 있다. (Advanced)

Codestates의 소프트웨어 엔지니어링 강의를 듣고 정리한 필기입니다. 😀

1. 재귀함수

1.1 재귀의 정의

재귀란 어떤 함수가 스스로를 호출하는 것을 뜻한다. 재귀를 이해할 때 factorial을 활용하는 것이 좋다.

▶ 펙토리얼이란 그 수보다 작거나 같은 모든 양의 정수의 곱이며, 기호는 !를 쓴다.

5!는 5 * 4 * 3 * 2 * 1라는 식과 같다. 즉, n!은 n 부터 1까지 곱하는 것을 말한다. 그런데 우리는 5! = 5 * 4 * 3 * 2 * 1을 5! = 5 * (4 * 3 * 2 * 1)라고 표현할 수 있다. 이때, (4 * 3 * 2 * 1)는 4!에 해당한다. 이런 방식으로 1!까지 나눌 수 있을 것이다. 아마 표현을 하면 5! = 5 * 4 * 3! 이 된다.

function fac (n) {
  if (n ===1) { // n 이 1일때는 더 이상 나눌 수 없기 때문에 
    return 1; 
  }
  return n * fac(n-1);
}

우리가 N펙토리얼을 함수로 만든다면, 이것을 계산할 때 스스로를 호출하는 재귀방법을 사용하게 될 것이다. (위 코드를 참고하자.)

재귀함수는 위처럼 중첩해서 들어가게 된다. 그렇다면 재귀는 return 혹은 더 이상 재귀를 할 수 없게 된다면 어떻게 될까?

재귀는 return 조건을 충족하거나 혹은 더 이상 재귀를 할 수 없을 때 한 층씩 거슬러 올라가며 함수가 실행된다.

1.2 재귀의 특징

재귀의 특징은 크게 두가지가 있다.

▶ 첫번째, 재귀는 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어질 수 있는 경우.

▶ 두번째, 중첩된 루프가 많거나 중첩의 정도를 미리 알 수 없는 경우.

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으로 표현이 가능하다. 하지만 재귀를 사용하는 이유는 재귀를 사용한 코드가 대부분 더욱 간결하고, 일부의 경우에는 이해하기도 쉽기 때문이다.