오늘은 재귀함수를 공부했습니다. 재귀함수가 나올 떄마다 이해가 안가서 재귀를 사용하면 코드 가독성이 떨어진다는 합리화를 하며 요리조리 피해다녔는데 오늘 정면으로 승부를 볼 수 있는 시간이었습니다.


재귀함수란?

재귀라는 의미는 자기 자신으로 되돌아 간다는 의미인데요, 자바스크립트에서 말하는 재귀는 자기 자신을 호출하는 것입니다. 그러니까 함수 내부 안에서 자신의 함수를 호출하는 것이지요.

1
2
3
4
5
function recursive() {
  console.log('hello world');

  recursive();
}

👉🏻 이렇게 정의한 함수를 함수 내부 안에서 호출하면 hello world를 무한으로 출력시킬 수 있습니다.


재귀함수, 언제 사용해야하는데?

  • 반복문을 사용할 때 호출 횟수가 명확하지 않을 때
  • 중첩된 반복문이 많을 때

이런 경우일 때 주로 재귀함수를 사용합니다.


재귀함수 활용방법에 대해서 알려드리자면,

우선 base case와 recursive case를 나눠서 생각해야합니다.

base case는 종료조건을 의미하고 recursive case는 반복으로 재귀함수를 호출해야하는 조건을 의미합니다. base case가 없으면 함수가 무한으로 호출되기 때문에 콜스택에 계속해서 함수가 쌓이는 현상을 경험할 수 있답니다.

🐛 일반적 재귀함수 템플릿

1
2
3
4
5
6
7
8
function recursive(input1, input2, ...) {
  // 탈출 조건
  if(재귀함수를 종료해야하는 경우){
    return
  }

  return recursive(); // 재귀조건
}

재귀 문제를 풀어봅시다.

오늘 풀어 본 문제 중에서 푸는데 시간이 오래 걸렸던 문제들을 다시 풀면서 정리해봅시다.

take

수(num)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴

입출력 예시

1
2
3
4
5
let output = take(2, [1, -2, 1, 3]);
console.log(output); // --> [1, -2]

output = take(5, [1, -2, 1, 3]);
console.log(output); // --> [1, -2, 1, 3]

✅ 문제 이해하기

  • num개의 요소를 가진 배열을 리턴해라!

  • recursive case

    • 배열의 length와 num이 다를 때 👉🏻 맨 뒤 요소를 제외한 배열을 만들어서 재귀 함수에 전달 후 호출

  • base case

    • 배열의 length와 num이 같을 때
    • num이 배열의 길이보다 크다면 바로 배열 값 그대로 리턴하고 종료

1
2
3
4
5
6
7
8
function take(num, arr) {
  if (num >= arr.length) {
    return arr;
  }
  if (arr.length === 0) return [];

  return take(num, arr.slice(0, arr.length - 1));
}

이게 간단한 코드인 것 같지만 왜 오래 걸렸냐면… 처음엔 num개의 요소를 뺀 배열을 리턴하라는 문제인 줄 알고 열심히 풀었지만, 계속해서 테스트 케이스를 통과하지 못하는 것을 보고 제가 잘못 풀고 있다는 것을 그제서야 깨달았습니다.

unpackGiftbox

선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴

입출력 예시

1
2
3
4
5
6
7
const giftBox = ['macbook', 'mugcup', ['eyephone', 'postcard'], 'money'];

let output = unpackGiftbox(giftBox, 'iphone');
console.log(output); // --> false

output = unpackGiftbox(giftBox, 'postcard');
console.log(output); // --> true

✅ 문제 이해하기

  • 배열 안에 있는 요소들을 탐색하면서 wish로 받은 값이 있는지 확인 후 boolean 값으로 리턴하자!
  • 현재 배열 안에 배열이 많은데? 👉🏻 flat 메서드로 배열을 평탄화 시키고 작업하자.
  • recursive case
  • base case
    • wish와 동일한 값이 있을 떄 true 리턴
    • giftBox.length가 0일 때 false 리턴

처음에 작성한 코드

1
2
3
4
5
6
7
8
9
function unpackGiftbox(giftBox, wish) {
  if (giftBox.length === 0) return false;

  // 중첩된 배열이 많으니 배열을 평탄화 시켜놓고 작업
  const newGiftBox = giftBox.flat(Infinity);
  if (newGiftBox[0] === wish) return true;

  return unpackGiftbox(newGiftBox.slice(1), wish);
}

배열 안에 배열이 너무 많기 때문에 배열을 먼저 평탄화 시키고 작업해야겠다!라는 생각이 먼저 들었고 배열의 첫 번째 요소값과 wish를 비교해서 같은지 확인작업을 진행했습니다. 만약 첫 번째 요소와 wish의 값이 다르다면 0번째 요소를 제외한 배열을 재귀 함수의 인수로 전달하고 후출하는 방식으로요.


이 코드를 실행시켜보면 1개의 테스트 코드를 실패한 것을 볼 수 있습니다.

.
alt
alt

재귀 호출 횟수가 최대 4번까지인 것 같은데 제 코드에서는 현재 7번의 재귀 호출이 일어나고 있습니다.

호출 횟수를 줄이려면 어떻게 하는게 좋을까..🤔 생각을 해보다가 배열의 1depth는 for문으로 순회하면 되겠다!라는 생각이 들었습니다.

이만큼 생각한 내 자신? 대단해


정리를 해보자면

우선 for문으로 배열을 순회한다.
➡️ i번째 요소가 wish와 같은 지 확인한다.
➡️ 만약 i번째 요소가 배열이라면, i번째 요소를 인수로 전달하고 재귀함수를 호출한다.

이 순서대로 간다면 재귀 호출 횟수를 줄일 수 있을 것 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function unpackGiftbox(giftBox, width) {
  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) {
      return true;
    }

    // ✅ i번째 요소가 Array인지 확인하기
    if (Array.isArray(giftBox[i])) {
      // 재귀 호출했을 떄 그 함수의 값이 true라면 true 리턴하기
      if (unpackGiftbox(giftBox[i], wish)) return true;
    }
  }

  return false;
}

테스트 통과😎


Review

재귀 함수를 썼던 경험이 많이 없다보니, 경우의 수를 생각하는데 시간이 오래 걸렸던 것 같습니다. 혼자서 공부했다면 계속해서 피해다녔을 것 같은데 오늘 수업 덕분에 정면승부할 수 있었던 것 같습니다.

그런데 실무에서는 재귀를 어떻게 쓸까요? 정말 혹시라도 실무자분들이나 재귀를 프로젝트에 사용해보신적이 있다면 답변을 남겨주셨으면 좋겠습니다.👏🏻