[Algorithm/JavaScript] Basic JavaScript: Use Recursion to Create a Range of Numbers

재귀함수를 사용하는 문제들은 늘 예상보다 시간이 더 소요되는 경향이 있는 것 같다.
다음에 다시 풀어볼 때는 30분보다는 짧게 걸리길...💪

---

문제출처: freecodecamp.org

문제

We have defined a function named rangeOfNumbers with two parameters. The function should return an array of integers which begins with a number represented by the startNum parameter and ends with a number represented by the endNum parameter. The starting number will always be less than or equal to the ending number. Your function must use recursion by calling itself and not use loops of any kind. It should also work for cases where both startNum and endNum are the same.

⇨ 즉, 매개변수 startNum으로 시작하고 endNum으로 끝나는 정수 배열을 반환하는 문제. startNum은 항상 endNum보다 같거나 작으며, 두 매개변수가 같은 값일 때에도 정상적으로 작동해야한다. 또한 반복문은 사용해서는 안되며, 반드시 재귀함수를 이용한 실행문을 작성해야한다.

function rangeOfNumbers(startNum, endNum) {
  return ; 
}

---

풀이과정

첫 오답:

function rangeOfNumbers(startNum, endNum) {
  if (startNum === endNum) {
    return [startNum];
  } else { 
    const num = rangeOfNumbers(startNum + 1, endNum)
    num.push(startNum);
    return num;
  }
};

문제화면 좌측에 제공된 예시를 참고한 후 첫 답변을 작성해 제출하니 어떤 건 맞고, 어떤 건 틀렸다는데... 🤔

rangeOfNumbers(4, 4) 의 반환값이 [4]가 맞다고 하는 걸 보니
위에 if (startNum === endNum) { return [startNum]; }는 잘 쓴 게 맞나보다.

그렇다면 else 이후 실행문이 틀렸다는 얘기인데...
혹시 재귀함수 부분rangeOfNumbers(startNum + 1, endNum)이 틀렸나..?
오답이 반환하는 값이 궁금해져 console을 찍어보았다.

console.log(rangeOfNumbers(1, 5));
// [5, 4, 3, 2, 1]

원하는 값은 오름차순인데, 나온 값은 내림차순이다.
그렇다면!!!! push()를 unshift() 메소드를 바꿔본다.

function rangeOfNumbers(startNum, endNum) {
  if (startNum === endNum) {
    return [startNum];
  } else { 
    const num = rangeOfNumbers(startNum + 1, endNum)
    num.unshift(startNum);
    return num;
  }
};

passed 👏 👏 👏
언제봐도 기분좋은 큼지막한 체크가 떴다 :)

그런데 여기서 갑자기 또 문득 궁금함이 생겼다.
const num으로 변수는 선언해줬다고 치자. 그런데 num이 배열인 건 어떻게 알지?
왠지 재귀함수에 답이 있을 것 같은 생각이...!

예를 들어 rangeOfNumbers(1, 5);의 경우, console.log(num)을 추가해서 실행시키며, 실행순서는 다음과 같다.

흠 뭔가 대충 감은 오는데 여전히 직관적이지가 않다.
재귀함수 실행순서를 단계별로 적어봐야겠다. ➡️ ➡️ ➡️

1) 먼저 매개변수 (1, 5)를 인자로 주어 실행시킨다.

function rangeOfNumbers(1, 5) { 
  if (1 === 5) { 
    return [1]; 
  } else { 
    const num = rangeOfNumbers(1 + 1, 5)
    /*여기서 위 코드는 rangeOfNumbers(1, 5)의 return값을
    반환하기 전 rangeOfNumbers(2, 5)를 실행시킨다. rangeOfNumbers(2, 5)의 
    값이 반환되기 전까지 여기에서 실행이 멈춰져있는 상태*/
    num.unshift(1);
    return num; 
  }
}; 

2) 이어서 rangeOfNumbers(1, 5)의 재귀함수(코드 const num = rangeOfNumbers(1 + 1, 5))는 return값이 반환되기 전 rangeOfNumbers(1 + 1, 5)를 실행시킨다.

function rangeOfNumbers(2, 5) { 
  if (2 === 5) { 
    return [2]; 
  } else { 
    const num = rangeOfNumbers(2 + 1, 5)
    /*여기서 위 코드는 rangeOfNumbers(2, 5)의 return값을
    반환하기 전 rangeOfNumbers(3, 5)를 실행시킨다. rangeOfNumbers(3, 5)의 
    값이 반환되기 전까지 여기에서 실행이 멈춰져있는 상태*/
    num.unshift(2);
    return num; 
  }
}; 

...
...
...

3) 같은 방식으로 rangeOfNumbers(4, 5) 가 될 때까지 재귀함수가 실행되다가,
rangeOfNumbers(5, 5)가 되면 return값이 반환된다.

function rangeOfNumbers(5, 5) { 
  if (5 === 5) { 
    return [5]; 
    /*여기서 if 조건문이 truthy가 되어 5를 요소로 가진 배열을 반환한다. 
    이곳에서 배열이 생겨나는 것이다!!*/
  } else { 
    const num = rangeOfNumbers(5 + 1, 5)
    num.unshift(5);
    return num; 
  }
}; 

4) 배열[5]를 반환받은 rangeOfNumbers(4, 5)가 num 변수에 [5]를 할당하고, 배열num의 0번째 인덱스에 요소 4를 추가한다.

function rangeOfNumbers(4, 5) { 
 if (4 === 5) { 
   return [4]; 
 } else { 
   const num = [5];
   //여기서부터 내부함수의 값을 반환받기 위해 멈춰져있던 재귀함수가 다시 실행된다.
   num.unshift(4);
   return num; 
 }
}; 

...
...
...

5) rangeOfNumbers(4, 5)는 값으로 배열num = [4, 5]를 반환하고, 이와 같이 재귀함수는 rangeOfNumbers(1, 5)가 값을 반환받을 때까지 연속적으로 내부 함수의 값을 반환한다.

function rangeOfNumbers(1, 5) { 
 if (1 === 5) { 
   return [1]; 
 } else { 
   const num = [2, 3, 4, 5];
   num.unshift(1);
   return num; 
 }
}; 

최종적으로 rangeOfNumbers(1, 5)가 배열 num의 값으로 [1, 2, 3, 4, 5]을 반환하며 함수 rangeOfNumbers 가 끝이난다.

---

오늘의 Lesson

• .push()는 array의 마지막에 요소를 추가, .unshift()는 array의 첫부분에 요소를 추가하는 메소드.
• 재귀함수는 리턴을 마치게 되면 가장 내부에 중첩된 함수부터 순차적으로 반환한다.
  재귀함수 기본개념 알기