[알고리즘 완전 정복] 재귀함수 3단계 작성법

학습 목표

재귀 함수의 정의와 원리 이해하기: 재귀 함수가 무엇인지, 자바스크립트의 실행 컨텍스트와 연결되어 어떻게 동작하는지 이해한다.
재귀 문제 해결 전략 익히기: 재귀적 사고 방식을 배우고, 적절한 종료 조건과 재귀 호출을 설계할 수 있다.

📌 [정의] 재귀함수의 뜻

아마 많은 분들이 피보나치(fibonacci) 함수와 같이 재귀함수의 기본적인 형태는 한번쯤 보신 적이 있을 것이라고 생각합니다. 예시를 보면서 이야기 해볼까요?

1
function countDown(n) {
2
  console.log(`Counting down: ${n}`);
3

4
  if (n === 0) {
5
    return;
6
  }
7

8
  countDown(n - 1);
9
}
10

11
countDown(3);

📌 재귀함수의 실행 흐름

실행 컨텍스트 (Execution Context)

재귀함수의 실행 흐름을 정확히 이해하기 위해서는 실행 컨텍스트에 대해 이해해야 합니다.

실행 컨텍스트 콜 스택

여러분께서 알고 계시는 콜 스택 구조는 사실 정확히 말하자면, 각각의 실행 컨텍스트가 쌓이는 공간입니다.

아래와 같은 예시 코드를 살펴봅시다.

예시 1.

1
function add(a, b) {
2
  return a + b;
3
}
4

5
const result1 = add(1, 2);
6
const result2 = add(result1, 3);
7
const result3 = add(result2, 4);
8
const result4 = add(result3, 5);
9
const result5 = add(result4, 6);

우리 자바스크립트 프로그램이 구동되면, 글로벌 실행 컨텍스트가 기본적으로 생성됩니다. 글로벌 실행 컨텍스트를 제외한다면, 위의 예시 코드에서는 몇 개의 실행 컨텍스트가 생성되었을까요?

add 함수가 5번 실행되었으므로, 5개의 실행 컨텍스트가 생성되었습니다. 물론 각 함수의 실행이 종료되는 시점에 폐기되기도 했습니다.

조금 다른 예시 코드를 한번 더 살펴봅시다.

예시 2.

1
function addTwo(a) {
2
  return a + 2;
3
}
4

5
let result = 0;
6

7
while (result < 6) {
8
  result = addTwo(result);
9
}

위의 예시 코드도 마찬가지로 우선 프로그램 초기 구동시 글로벌 실행 컨텍스트가 생성됩니다. 그 외에는 몇 개의 실행 컨텍스트가 생성되었을까요?

result가 6일때 while문의 조건을 탈출하게 되므로, addTwo 함수가 총 3번 실행되었겠죠? 그러므로 총 3개의 실행 컨텍스트가 각각 생성되어 콜 스택에 쌓였다가 종료되며 제거되었을 것입니다.

순서	실행 구문	실행 컨텍스트
첫 번째	`addTwo(0);`	`a` 매개변수의 값은 0이라는 정보가 실행 컨텍스트에 담겨 있습니다.
두 번째	`addTwo(2);`	`a` 매개변수의 값은 2이라는 정보가 실행 컨텍스트에 담겨 있습니다.
세 번째	`addTwo(4);`	`a` 매개변수의 값은 4이라는 정보가 실행 컨텍스트에 담겨 있습니다.

예시 3.

이제 간단한 재귀함수의 실행 흐름을 한번 살펴볼까요?

📌 작성 팁

1. 종료 조건을 작성하고 확인할 것

위의 예시 코드에서 눈치 채셨을 수 있지만, 재귀함수에서 가장 중요한 것은 로직의 탈출구, 즉 종료 조건을 마련하는 것입니다.

이제는 다들 아시겠지만, 재귀함수는 자기 자신을 다시금 호출하는 함수를 일컫습니다. 자기 자신을 계속 다시 호출한다면, 끝없이 반복하겠죠? 이 끝없는 반복을 끝내기 위해서는 탈출해야 하는 종료 조건이 있어야만 합니다.

예를 들어, 위의 예시 3번, countDown 함수에서는 n === 0과 같은 로직이 그 종료 조건이 될 수 있습니다.

많은 이들이 종료 조건이 필요하다는 것을 알고 있지만, 이와 관련하여 자주 실수하는 부분이 있습니다.

예시 4.

아래와 같은 예시 코드는 종료 조건이 존재하는 것처럼 보입니다. 실제로 실행시킬 경우 어떻게 될까요?

1
function stopIfEven(n) {
2
  if (n % 2 === 0) {
3
    return;
4
  }
5

6
  stopIfEven(n - 2);
7
}
8

9
stopIfEven(101);

물론 위의 예시 코드는 과장된 예시로서 너무나도 명백히 종료 조건이 실행되지 않는다는 것이 눈에 보이지만, 실제 작업을 하는 상황에서도 이와 비슷한 경우가 매우 빈번히 발생합니다.

실제로 종료 조건을 작성했는지가 중요한 것이 아닙니다. 종료 조건이 실제로 실행되는지가 중요한 것입니다.

2. 반드시 `debugger`를 활용할 것

종료 조건이 실제로 실행되는지에 대한 여부는 어떻게 확인하는 것이 좋을까요?

이 순간 만큼은 debugger를 반드시 시도하셔야 합니다.

debugger는 우리 코드의 실행 흐름을 아주 샅샅이 쫓아가며 살펴볼 수 있도록 돕는 기능입니다.

시간이 걸리더라도, 현재 살펴보는 코드에 대해 100% 이해하고 의심의 소지가 없도록 하고 넘어가는 것이 좋습니다. 그렇지 않으면, 결국 돌아와 중복된 시간 투자가 필요해질 수 있습니다.

급하게 서두르지 마세요. 한번 할때 확실하게 하세요.

아직 debugger를 사용해본 적이 없으시다구요? 괜찮습니다. 지금 제가 간단히 알려드리겠습니다.

Step 1

브라우저 개발자 도구를 열고 콘솔창에 아래의 코드를 입력해보세요.

1
function countDown(n) {
2
  if (n === 0) {
3
    return;
4
  }
5

6
  countDown(n - 1);
7
}
8

9
debugger;
10
countDown(3);

Step 2

아래와 같은 상태로 진입하셨나요?

debugger-1

제가 빨간 박스로 표시한 4개의 버튼을 이용하여 우리는 디버깅 과정을 제어할 것입니다.

버튼 이름	아이콘	기능
Play		멈춤과 재생을 할 수 있는 버튼입니다.
Step over		다음 실행구문으로 이동하는 버튼입니다. 비유적으로 설명하자면, 다음 줄로 이동한다고 이해하셔도 괜찮습니다.
Step in		함수 실행문을 만났을때, 해당 함수 내부로 진입할 수 있는 버튼입니다.
Step out		함수 내부로 진입한 상태에서 다시 빠져나갈 수 있는 버튼입니다.

Step 3

개발자 도구에서 Step OVER 버튼을 1회 클릭해보세요. 아래와 같은 상태로 변경될 것입니다.

debugger-2

함수 실행문을 만난 상태가 되었습니다. 현재 상태는 countDown(3);이라는 함수 실행문이 실행되기 직전인 상태입니다.

함수 실행문의 내부로 진입하여 조금 더 자세한 내용을 살펴보고 싶다면, Step in을 이용해 살펴볼 수 있습니다.

Step 4

개발자 도구에서 Step IN 버튼을 1회 클릭해보세요. 아래와 같은 상태로 변경될 것입니다.

debugger-3

좌측의 빨간 박스를 보시면, 현재 n이라는 매개변수의 값이 표기되고 있어 매우 유용합니다. 또한 현재 연산 중인 구문(조건문)의 색깔이 조금 더 진하게 표기되는 것을 확인할 수 있습니다. 이 뿐만 아니라, 변수에 마우스를 올리면 해당 변수의 값을 확인할 수도 있습니다.

신기한 기분이 든다면, 아직 파티는 이릅니다.

우측의 파란 박스를 보시면, 해당 스코프 내부의 모든 변수 정보를 한 눈에 확인할 수 있고 콜 스택 또한 쉽게 확인할 수 있습니다. 콜 스택에 쌓인 실행 컨텍스트들을 클릭하여 콜 스택에 쌓여있는 함수 실행문 간에 이동하며 다시 확인할 수도 있는 기능도 있습니다.

Step 5

개발자 도구에서 Step OVER 버튼을 1회 → Step IN 버튼을 1회 클릭해보세요. 아래와 같은 상태로 변경될 것입니다.

debugger-4

n의 값이 2로 변경되어 countDown 함수가 실행된 것을 확인할 수 있으신가요?

콜 스택 또한 확인해보시면 새로운 실행 컨텍스트가 쌓인 것을 확인할 수 있습니다.

이제 Step out 기능도 한번 사용해볼까요?

Step 6

기억하실지 모르겠지만, 방금 Step 5에서 우리는 Step in을 이용하여 countDown 함수 실행문 내부로 진입해 있는 상태입니다. 그렇기에 Step out을 사용할 수 있습니다.

자, 그렇다면 이제 개발자 도구에서 Step OUT 버튼을 1회 클릭해보세요.

debugger-5

다시 n이 3이던 이전 함수 실행 시점으로 되돌아 왔고, 콜 스택에서도 실행 컨텍스트가 하나 제거되어 있는 것을 확인할 수 있으신가요? 우리가 n = 2 였던 함수 실행문으로부터 빠져나왔기 때문에 해당 함수 실행에 대한 실행 컨텍스트가 제거된 것입니다.

Step 7

이렇게 자세히 코드의 흐름을 살펴보는 과정에서 우리가 원하는 정보를 모두 취득하고, 이제 빠져나가고 싶은 시점이 생길 수 있겠죠?

자, 이제 Play 버튼을 1회 클릭해보세요.

debugger-6

모든 디버깅 과정이 종료되고, 우리의 코드 실행문들이 재개되어 코드 실행이 종료되는 것을 확인할 수 있습니다.

`debugger` 응용법

debugger도 결국 코드입니다. 즉, 조건문이나 기타 로직에 따라 debugger 구문의 실행을 제어할 수 있습니다.

사실 단순한 사실인데, 의외로 많은 사람들이 깜짝 놀라는 부분입니다.

1
function countDown(n) {
2
  if (n === 1) {
3
    debugger;
4
  }
5

6
  if (n === 0) {
7
    return;
8
  }
9

10
  countDown(n - 1);
11
}
12

13
countDown(3);

3. 재귀를 구현하려 하지 말 것

소제목이 조금 어그로가 있기는 하지만, 나름대로 의미가 있으니 주의깊게 봐주시기 바랍니다.

재귀를 처음 접하시는 분들이 재귀를 시도해보기 가장 좋은 로직은 재귀적인 탐색이라고 생각합니다. 재귀적인 탐색이란, 아래와 같은 경우를 의미합니다.

예를 들어, 우리가 document.getElementById과 같은 기능을 하는 함수를 작성한다고 생각해봅시다.

document.body를 시작점으로 하여, 모든 자식 요소들의 아이디를 확인해야 합니다. 만약 자식 요소들이 또 자식 요소들을 갖고 있다면, 그 자식 요소들 또한 확인해야 합니다. 웹 페이지는 웹 페이지마다 구조가 다르기 때문에, 우리는 문서의 끝이 어디인지 예측할 수 없습니다.

요소들을 탐색하는 과정의 종료 조건은 두 가지 중 하나가 충족 되어야 합니다.

원하는 아이디를 가진 요소를 찾았을 경우
모든 문서를 탐색했지만, 원하는 아이디를 가진 요소를 찾지 못했을 경우

재귀가 익숙치 않은 분들이 흔히 하는 실수 중 하나는, 너무 많은 것들을 한번에 다 성취하려고 한다는 것입니다. 그러다보니 모든 단계를 건너 뛰고, 완성체의 재귀함수를 이미 머릿속에 염두하고 코드를 작성하려 합니다. 하지만 문제는 머릿속에 염두해두었던 완성체의 재귀함수가 잘못된 로직이었다는 것입니다.

그렇기 때문에 저는 더더욱 재귀를 의식하지 말고 실제로 구현해야 하는 로직을 1차적으로 작성해보라고 말씀드립니다. 모든 재귀함수에 적용 가능한 것은 아니지만, 재귀적인 탐색을 구현하는데 있어서는 이 접근 방향이 가능하고, 매우 많은 재귀함수가 탐색 로직입니다. 그렇기에 아주 좋은 훈련 방식이 될 것입니다.

재귀를 의식하지 말고 실제로 구현해야 하는 로직을 작성해보라는 의미는 무엇일까요? 아래 예시를 통해 한번 보여드리겠습니다.

반복되는 로직을 최소한 3차례 작성하자

1
function getElementById(id) {
2
  const root = document.body;
3

4
  for (let i = 0; i < root.children.length; i++) {
5
    const child = root.children[i];
6

7
    if (child.id === id) {
8
      return child;
9
    }
10
  }
11
}

우선 document.body를 기준으로 1단계 깊이의 자식 요소들만을 탐색하는 로직을 작성했습니다. 만약 아이디가 일치하는 요소를 찾게 된다면 다행이지만, 그렇지 못하다면 우리는 자식 요소들의 자식 요소들을 또 다시 탐색해야 합니다. 저는 그 로직 또한 계속 작성해보겠습니다.

1
function getElementById(id) {
2
  const root = document.body;
3

4
  for (let i = 0; i < root.children.length; i++) {
5
    const child = root.children[i];
6

7
    if (child.id === id) {
8
      return child;
9
    }
10

11
    if (child.children.length) {
12
      for (let j = 0; j < child.children.length; j++) {
13
        const grandChild = child.children[j];
14

15
        if (grandChild.id === id) {
16
          return grandChild;
17
        }
18
      }
19
    }
20
  }
21
}

document.body를 기준으로 2단계 깊이의 자식 요소들까지 탐색하는 로직을 작성했습니다. 하지만 여기서도 끝이 아닙니다. 이쯤되면 많은 사람들은 인내심을 잃고 훨씬 더 예쁜 코드를 쓰기 위해 급발진 하겠지만, 저는 상황을 조금 더 지켜보며 못생긴 코드를 작성해보겠습니다.

1
function getElementById(id) {
2
  const root = document.body;
3

4
  for (let i = 0; i < root.children.length; i++) {
5
    const child = root.children[i];
6

7
    if (child.id === id) {
8
      return child;
9
    }
10

11
    if (child.children.length) {
12
      for (let j = 0; j < child.children.length; j++) {
13
        const grandChild = child.children[j];
14

15
        if (grandChild.id === id) {
16
          return grandChild;
17
        }
18

19
        if (grandChild.children.length) {
20
          for (let k = 0; k < grandChild.children.length; k++) {
21
            const greatGrandChild = grandChild.children[k];
22

23
            if (greatGrandChild.id === id) {
24
              return greatGrandChild;
25
            }
26
          }
27
        }
28
      }
29
    }
30
  }
31
}

자, 이제 3단계 깊이까지 작성했습니다. 코드를 보니 어떤 흐름이 보이시나요? 공통적인 흐름이 보이시나요? 3번 정도 반복해서 작성해보니, 시간은 조금 소요되었지만 반복되는 패턴이 눈에 더욱 뚜렷하게 나타나게 된 것 같습니다.

1
function getElementById(id) {
2
  const root = document.body;
3

4
  // document.body는 항상 `children`이 존재하기 때문에 조건문이 생략되었습니다.
5
  for (let i = 0; i < root.children.length; i++) {
6
    const child = root.children[i];
7

8
    if (child.id === id) {
9
      return child;
10
    }
11

12
    if (child.children.length) {
13
      for (let j = 0; j < child.children.length; j++) {
14
        const grandChild = child.children[j];
15

16
        if (grandChild.id === id) {
17
          return grandChild;
18
        }
19

20
        if (grandChild.children.length) {
21
          for (let k = 0; k < grandChild.children.length; k++) {
22
            const greatGrandChild = grandChild.children[k];
23

24
            if (greatGrandChild.id === id) {
25
              return greatGrandChild;
26
            }
27
          }
28
        }
29
      }
30
    }
31
  }
32
}

우리가 이제 해야 할 일은 조금 더 뚜렷해졌습니다. 눈에 보이는 공통 로직을 재귀함수로 만드는 것입니다. 하지만 이 과정에서 몇 가지 신중히 처리해야 할 부분들이 있습니다.

반복되는 공통 로직에서 차이점을 찾도록 하자

현재 공통 로직을 잘 보시면 차이점이 있습니다. 6번째 줄, 14번째 줄, 22번째 줄의 대상이 각각 root, child, grandChild로 변경되고 있는 것입니다. 변경되는 부분은 어떻게 처리하면 좋을까요?

잘 생각해보시면 우리는 현재 재귀함수를 만들려고 하고 있습니다. 함수에서 가변적인 값을 처리하는 가장 손쉬운 방법은 무엇일까요? 그렇죠, 바로 매개변수입니다. 반복되는 패턴 속에서 변하는 부분을 찾고, 변하는 값들은 매개변수로 처리되도록 재귀함수를 만들어주면 됩니다.

1
function getElementById(targetElement, id) {
2
  if (targetElement.children.length) {
3
    for (let i = 0; i < targetElement.children.length; i++) {
4
      const child = targetElement.children[i];
5

6
      if (child.id === id) {
7
        return child;
8
      }
9

10
      getElementById(child, id);
11
    }
12
  }
13
}
14

15
const result = getElementById(document.body, "some-id");

한 단계 진보한 것은 사실이지만, 아직 완성되지 않았습니다. 이렇게 작성해놓고 “왜 안되지?”라고 고민하고 있는 분들의 뒷모습을 볼때가 많습니다.

매우 중요한 부분이 남았습니다.

재귀함수들의 반환값들을 연결하자

1
function getElementById(targetElement, id) {
2
  if (targetElement.children.length) {
3
    for (let i = 0; i < targetElement.children.length; i++) {
4
      const child = targetElement.children[i];
5

6
      if (child.id === id) {
7
        return child;
8
      }
9

10
      getElementById(child, id);
11
    }
12
  }
13
}
14

15
const result = getElementById(document.body, "some-id");

getElementById 함수가 실행되고, 6번째 줄의 조건문이 충족되지 않아 10번째 줄의 재귀함수가 호출되었다고 가정해봅시다. 우리는 10번째 줄의 재귀함수가 어떤 반환값을 돌려주기를 기대하고 그 반환값이 결과값으로 연결되기를 기대할 것입니다.

10번째 줄의 재귀함수 실행문이 동일한 아이디를 가진 요소를 찾았다고 상황을 가정하고, 해당 반환값으로 치환해보겠습니다.

1
function getElementById(targetElement, id) {
2
  if (targetElement.children.length) {
3
    for (let i = 0; i < targetElement.children.length; i++) {
4
      const child = targetElement.children[i];
5

6
      if (child.id === id) {
7
        return child;
8
      }
9

10
      someElementWithSameId;
11
    }
12
  }
13
}
14

15
const result = getElementById(document.body, "some-id");

여러분이 현재 보시는 위의 getElementById 함수에서 someElementWithSameId를 “반환(return)“해주어야 15번째 줄의 result 변수에 올바른 결과가 전달되게 되는데, 현재 작성한 코드대로라면 그 연결고리가 끊겨있는 상태인 것입니다.

그리고 document.getElementById는 원하는 요소를 찾지 못했을때 null을 반환한다는 부분을 감안하여 우리의 로직을 최종적으로 보완한다면 아래와 같은 결과물이 나올 수 있습니다.

1
function getElementById(targetElement, id) {
2
  if (targetElement.children.length) {
3
    for (let i = 0; i < targetElement.children.length; i++) {
4
      const child = targetElement.children[i];
5

6
      if (child.id === id) {
7
        return child;
8
      }
9

10
      const result = getElementById(child, id);
11

12
      if (result) {
13
        return result;
14
      }
15
    }
16
  }
17

18
  return null;
19
}
20

21
const result = getElementById(document.body, "some-id");

재귀함수 작성법 정리

우리가 작성해야 하는 로직은 어떤 흐름일까요? 먼저 재귀를 사용하지 않고, 위에서 설명드린 것처럼 반복되는 로직의 흐름을 구현해보세요.
작성한 코드에서 반복되는 로직의 패턴을 찾아보세요. -> 반복되는 로직이 재귀함수가 되어야 합니다.
반복되는 패턴에서 변경되는 부분이 있는지 확인해보세요. -> 재귀함수의 매개변수로 설정되어야 합니다.
종료되어야 하는 조건을 추가해보세요.
재귀함수가 실행되는 부분의 반환값을 받아서 처리할 필요가 있는지 확인해보세요.
기대하는 것과 다르게 실행된 부분이 있다면, debugger를 활용하여 코드를 살펴보세요.

재귀함수 실습 예제

중첩 배열 평탄화 하기

입력값 예시

const nestedArr = [1, [2, [3, [4, 5], 6, [7, 8, [9, 10]]]]];

function flatten(arr) {
  // TODO
}

결과값 예시

const result = flatten(nestedArr);
console.log(result); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

추가 학습자료

모던 자바스크립트 [재귀와 스택]

처음 접하는 재귀는 어렵지만, 알고보면 재미있습니다. 1-2주일 내에 친숙해지기는 어렵겠지만, 시간을 갖고 꾸준히 다가가 보시면 좋을것 같습니다.