26일차, 재귀함수

2021. 08. 24 화요일

1. Today's Key Point!🔑

• 재귀함수
• 코플릿

2. 정리해보자!🧹

재귀함수는 자기자신을 호출하는 함수이다.

그래서 재귀함수를 어떨때 사용하면 좋은가? 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우.

모든 재귀함수는 반복문으로 표현할 수 있다. 하지만 재귀를 적용할 수 있는 대부분의 경우에는 재귀를 사용하는 것이 코드가 더욱 간결해지고 이해하기가 쉽다. 고 하는데 나는 아직 재귀함수에 익숙하지 않아서 그런지 이해하는 것이 만만치 않았다. 계속 쓰면서 익숙해지다보면 while이나 for를 쓰는것보다 편해지지 않을까 싶다.

그래서 재귀함수 어떻게 쓰는가? Base Case와 Recursive Case로 잘 나누어서 생각하는 것이 중요하다. Base Case는 재귀의 탈출 조건을 구성한다. 그리고 Recursive Case에서 남아있는 복잡한 경우를 해결한다. 반복문while로 비교를 하자면 while안의 조건으로 들어가는 부분이 Base Case로 들어가고, 반복문을 실행해주는 부분이 Recursive로 들어간다고 생각하면 될 것이다. 글로만 보면 이해하기 어렵기 때문에 factorial로 재귀함수에 대해 알아보자.

우선 반복문으로 팩토리얼을 구현해보면

function factorial(num) {
  const result = num;
  while(num > 1){
    result = result * (num - 1);
    num--
  }
  return result;
}

이렇게 될 것이다. 위의 반복문을 보면 while안에 조건이 반복문이 끝나게 되는 조건이 되는데 저 부분이 재귀함수의 Base Case로 간다고 보면 된다. 그리고 조건문 안에서 실행되는 부분이 Recursive Case로 간다고 보면 된다.

function factorial(num) {
  //Base Case num이 0이 되면 재귀함수 탈출!
  if(num === 0) return 1;
  //Recursive Case
  return num * factorial(num - 1);
}

반복문에서도 그렇듯이 조건을 잘못 주면 무한루프에 빠지게 된다. 재귀함수도 마찬가지로 위의 함수로 예를 들면, Base Case 부분에 num === 0 일때 1을 리턴하라는 조건을 넣지않으면 팩토리얼 함수는 무한루프에 빠지게 될 것이다.

그럼 저 재귀함수가 어떤원리로 돌아가는지 좀 더 자세히 보자.

function factorial(4) {  // 함수에 4를 넣는다고 가정해보자.
  //Base Case num이 0이 되면 재귀함수 탈출!
  if(num === 0) return 1;
  //Recursive Case
  return 4 * factorial(3) {
               if(num === 0) return 1;
               return 3 * factorial(2){
                            if(num === 0) return 1;
                            return 2 * factorial(1){
                                         if(num === 0) return 1;
                                         return 1 * factorial(0) = 0
         4          * 3          * 2          * 1      * 1 = 24
} //결국 24가 리턴되게 된다.
 
 

3. 코플릿 복기!🧐

가장 애먹은 문제를 복기해보겠다.

다차원의 배열을 입력받아서 1차원 배열로 변환해서 리턴해야하는 문제이다.

예를 들어, 함수에 [1, 2, [[[3, 4], 5], 6, 7], 8] 이런 다차원 배열을 입력하면 [1, 2, 3, 4, 5, 6, 7, 8]이 나오게 해야한다.

그럼 우선 어떻게 해줘야할지 생각해보자. 빈 배열을 하나 만들어주고, 입력한 배열의 요소를 하나씩 넣어주는데

입력한 배열의 요소가 배열이라면 그 배열을 풀어서 넣어주면 될 것이다.

그럼 코드를 짜보자.

function flattenArr(arr) {
  const result = []; // 빈 배열을 만들어서 여기에 arr요소를 하나씩 추가할 것이다.
  for(el of arr){ // arr 요소를 처음부터 하나씩 조회한다.
    if(Array.isArray(el)){ // 근데 arr 요소가 배열이면
      const newArr = flattenArr(el); // flattenArr함수에 요소를 넣어서 새로운 배열을 리턴 받는다.// 이 과정에서 배열이 계속 풀리게 된다.//arr안의 요소(el)가 배열이면 그 배열(el)을 자기자신 함수에 넣어주면 결국 그 배열(el)만 관리하기 때문에 브라켓 하나를 풀어주는 꼴이 된다.//그럼 결국 배열이 다 풀린채로 result에 담기게 될 것이다.
// 이 과정을 말로 설명하기가 너무 어렵다. 콘솔에 디버그를 찍어보면 어떻게 되는지 이해하기가 더 쉬울것이다.
      result.push(...newArr) //그 리턴 받은 배열의 요소만 result에 넣어준다. 
    }
    else{
      result.push(el); //요소를 하나씩 result에 추가해 준다.
    }
  }
  return result; //결국 1차원 배열을 얻을 수 있게 된다.
}

재귀함수.. 너무 어려운것 같다. 근데 이 문제를 재귀함수 없이 풀라고 하면 더 어려울 것 같다. 반복문을 몇개를 써줘야할지 감도 잘 안온다. 이 문제를 통해서 재귀함수를 왜 사용해야 하는지를 느낄 수 있었던 것 같다. 아직까지는 재귀함수에 익숙하지 않아서 재귀함수로 어떻게 해결해줘야 할지에 대한 솔루션을 한 번에 제시하지는 못하겠다. 재귀함수 코플릿을 다시 한번 정주행 하면서 재귀함수에 익숙해지는 시간을 가져야 할 것 같다.