SEB 섹션2. 2일차 TIL - 재귀 JavaScript

 

 

오랜만에 머리를 쓴다는 느낌을 받는 구간이었다. 이전에 파이썬을 할 때도 재귀에 대해서 경험해봤지만 당시에는 재귀를 공부하다가 빡쳐서 그 부분을 거의 스킵하듯이 넘어가서 이번에는 좀 제대로 녀석을 학습할 수 있었던 것 같다.

물론 일부분에서 재귀를 사용하면 편리하다는 것은 알지만 역시 해도 해도 적응이 안 되는 녀석이다.

base case를 조금만 잘못 설계하면 stack overflow가 발생되기 때문에 별로 손대고 싶지 않은 느낌만 가득하다.

---

재귀 Recursion

이름부터 무언가 주변 친구 중에 이름이 '재귀'라고 된 녀석이 있다면 평생 놀려줬을 것 같다.

우선 재귀의 의미부터 알아보자...

친절한 네이버 사전

그 의미는 위와 같이 네이버 사전에서 친절하게 알려준다. 그냥 요약하자면 특정 함수 안에서 그 함수가 반복되는 것을 의미한다. 사실 처음 재귀함수를 경험해보면 경외심과 함께 '이딴 걸 왜 쓰지?' 라는 생각이 가득해진다.(나도 그랬다) 하지만 사용해 볼수록 나름의 이유를 찾을 수 있었다.

 

재귀의 반복

재귀의 기능을 단순하게 정리하면 반복기능이다. (이건 네이버 사전에서도 언급하고 있으니까 반박 하지마셈)

그리고 모든 재귀는 while, for 반복문으로 표현이 가능하다. 아래 예시를 하나 살펴보자.

 

const intSum = (num) => {
  let sum = 0;
  for (let i = num; i > 0; i--) {
    sum += i;
  }
  return sum;
};

console.log(intSum(5)); // => 15

 

위 코드를 보면 알겠지만 for 반복문을 활용하여 주어진 매개변수 num의 값을 -1씩 연산하여 1 ~ num 까지의 정수를 모두 더하는 함수다. 그리고 위 코드를 재귀로 표현하면 아래와 같다.

 

// 재귀
const intSum = (num) => {
  if (num === 1) {
    return 1;
  }

  return num + intSum(num - 1);
};

console.log(intSum(5)); // => 15

 

보이는 것과 같이 반복문을 돌리지는 않지만 반복문을 돌리는 경우와 같은 결과값을 확보할 수 있다. 이처럼 기존 반복문과 같은 기능을 수행하는 것으로 이해할 수 있다.

 

재귀를 쓰는 이유

재귀를 쓰기 적합한 상황은 다음과 같다.

 

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

 

1번의 내용은 앞서 살펴본 intSum함수에 적용될 수 있는 경우다. 그렇다면 2번의 경우는 어떨까?

구체적으로 어떤 상황인지 정확하게 감이 오질 않는다. 아래 예시 배열을 보자

 

const arr = [0, [0, [0, [0, [0, 1, 2], 2], 2], 2], 2]

 

위 경우는 5개의 배열이 중첩된 구조인데 가장 안쪽에 있는 배열을 제외하고 모든 배열이 1번째 인덱스에 배열을 가진다. 그렇다면 여기서 가장 안쪽 배열에 있는 1의 값이 있는 인덱스를 가져오고 싶을 때는 어떻게 해야될까?

여기서 전제로 우선 중첩된 배열의 수(5)를 우리가 알고 있고 몇번째 인덱스에서 배열이 중첩되는지 모른다 그리고 가장 안쪽 배열에서도 1이 몇번째 인덱스인지 모른다고 가정해본다. 그렇다면 일반 반복문으로 표현하면 다음과 같이 쓸 수 있을 것이다.

 

const arr = [0, [0, [0, [0, [0, 1, 2], 2], 2], 2], 2];

const findOne = (arr) => {
  // 첫번째 배열 선회
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      // 두번째 배열 선회
      for (let j = 0; j < arr[i].length; j++) {
        if (Array.isArray(arr[i][j])) {
          // 세번째 배열 선회
          for (let k = 0; k < arr[i][j].length; k++) {
            if (Array.isArray(arr[i][j][k])) {
              // 네번째 배열 선회
              for (let l = 0; l < arr[i][j][k].length; l++) {
                if (Array.isArray(arr[i][j][k][l])) {
                  // 다섯번째 배열 선회
                  for (let m = 0; m < arr[i][j][k][l].length; m++) {
                    if (arr[i][j][k][l][m] === 1) {
                      return m;
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
};

console.log(findOne(arr)); // => 1

 

그냥 보기만 해도 코드에 하자가 많아 보인다. 일단 생긴게 너무 후줄근해보이기 그지 없다. 그렇다면 재귀로 저걸 표현해보면 다음과 같다.

 

const arr = [0, [0, [0, [0, [0, 1, 2], 2], 2], 2], 2];

const findOne = (arr, idx) => {
  const head = arr[0];
  const tail = arr.slice(1);

  if (head === 1) return idx;

  if (Array.isArray(head)) return findOne(head, 0);
  else return findOne(tail, idx + 1);
};

console.log(findOne(arr, 0)); // => 1

 

재귀로 위와 같이 작성된다면 앞서 일반 반복문에 대한 전제조건 중에서 중첩된 배열 수를 몰라도 된다. 재귀에 적합한 상황 2번은 이렇게 이해할 수 있을 것이다. 그리고 심지어 위의 덕지덕지 붙인 for 반복문보다 훨씬 깔끔하게 코드를 작성하고 이해하는데도 좀 더 쉽게 코드를 이해해볼 수 있다.

 

Stack Overflow

파이썬에부터 재귀를 공부해왔지만 어떤 언어든 간에 재귀를 잘못 쓰면 stack overflow가 발생된다. 이 경우는 무한반복에 빠지는 경우이다. 이에 대해서 이해하려면 call stack에 대해서 알아야한다. 

 

나도 call stack이 뭔지는 정확하게 이야기 할 순 없지만, 간단하게 보면 함수가 실행될 때 생성되는 함수의 실행 명령 내용이다. 즉 함수 하나에 call stack하나가 생긴다고 보면된다. 이것과 관련해서는 후입선출 등등 설명할 게 많지만 이야기하면 끝도 없으므로 이 정도면 여기서 충분히 설명이 될 듯 하다. 여기서 명심할 부분은 함수 1개 = stack 1개라는 점이다.

(stack이 overflow다? === 함수가 overflow다!)

 

재귀함수는 이 부분에서 조금 취약할 수 있다. 재귀의 근본은 함수에서 또 함수를 실행시켜 반복효과를 보는데 즉 우리는 단순히 함수 1개를 실행시킴에도 스택은 그 이상이 쌓이는 경우가 발생된다.

 

 

위에서 다루었던 findOne 재귀함수를 vs코드에서 디버깅 해보면 3번째 배열에서 위와 같은 화면을 볼 수 있다. 저기서 왼쪽 아래를 보면 호출스택이라는 부분에서 findOne이라는 스택이 3개 쌓인 것을 볼 수 있다. 즉, findOne함수가 3개 쌓인 것이다. 당연히 함수 안에서 함수 본인을 다시 호출하면서 저런 추가적인 스택이 쌓이는 것이다. 재귀가 실행되는 것을 시각적으로 확인해보면 이에 대한 이해가 더 빨라질 수 있다.

 

피보나치 재귀함수의 실행 트리

 

피보나치 함수를 재귀로 구현하고 실행하게 되면 위와 같이 스택이 발생된다고 이해해볼수도 있다. 저 경우 재귀함수는 특정한 조건에 도달될 때까지 지속적으로 재귀함수를 호출하고 이는 스택에 계속 쌓인다. 그리고 위 그림에서의 각 트리의 끝에 도달하면 특정한 조건에 의하여 특정한 값이 return되는 등의 경우가 생기면 펼쳐놓았던 stack을 거꾸로 하나씩 처리한다.

(vs코드 등에서 디버깅 기능을 활용하여 재귀함수 작동 시 호출스택의 변화를 보면 최대치까지 스택이 생긴다음 줄어드는 것을 확인 할 수 있다.)

 

이제부터는 stack overflow를 설명하기가 쉬워진다. 즉, 위 그림에서 트리의 끝이라고 인식될 수 있는 특정한 조건이 지속적으로 충족되지 않기 때문에 스택이 메모리가 감당하기 어려운 수준까지 펼쳐지면 stack overflow라는 에러가 생기는 것이다.

 

재귀의 Base case

앞에서 stack overflow를 이야기하면서 계속해서 다루었던 특정한 조건은 재귀에서 base case라고 부른다. 재귀의 escape case, 탈출 구문 이라고 불리는 것은 모두 base case와 같은 말이다.

 

// 재귀
const intSum = (num) => {

  // base case
  if (num === 1) {
    return 1;
  }

  return num + intSum(num - 1);
};

console.log(intSum(5)); // => 15

 

앞서서 예시로 다루었던 정수의 합을 다루는 재귀함수에서 base case는 if문 안의 내용이라고 볼 수 있다. 저 부분은 사실상 일반 반복문에서 볼 때 for의 실행 조건문과 동일한 역할을 한다고 볼 수 있다. 하지만 일반적으로 알고 있는 반복문에서의 조건문과 생겨먹은 부분이 다르고 쓰는 방법에 조금 변형이 있을 수 있어 처음 재귀를 배울 때 굉장히 난감했던 기억이 있다.