[코딩노트] S3 Unit 1. 재귀함수

💡 이 포스트에는 S3 Unit 1. 재귀함수와 관련된 코딩과제를 하고 몰랐던 점이나 부족했던 점을 정리했다!
(누군가에게는 너무 쉬워 하품이 나올 수 있습니다.🥲)

코딩노트 정리하기

이번에는 재귀함수를 호출하여 문제를 풀었다.
재귀함수를 활용하는 핵심 방법은

• 공통적인 패턴을 찾아 재귀함수를 호출하는 recursive 부분과,
• 재귀함수로 쪼갤 수 없는 탈출 조건인 base 부분을 찾아내는 것이다.

재귀함수를 활용하는 더 자세한 방법은 아래의 포스트에 정리하였다.
🔗 S3 Unit 1. [자료구조/알고리즘] 재귀

참고로 아래의 몇몇 문제들은 굳이 재귀함수를 사용하지 않고 반복문을 사용해도 풀 수 있으나, 이번에는 재귀함수의 패턴에 익숙해지기 위해 재귀함수를 사용하였다.

1. 1부터 n까지의 합 구하기

recursive : n까지의 합=n + (n-1)까지의 합
base : 1까지의 합은 1, 0까지의 합은 0
1에서 4까지의 합은 4+(1에서3까지의 합),
1에서 3까지의 합은 3+(1에서2까지의 합)...
이렇게 정리하다보면 0과1은 더 쪼갤 수 없기에 base case가 되고,
나머지는 n까지의 합=n + (n-1)까지의 합이 된다.
이를 코드로 나타내보면 아래와 같다.

function sumAll(n){
  //base
  if(n<=1) return n; //1의 경우, 0의 경우를 합칠 수 있다.
  //recursive
  return n+sumAll(n-1); 
}

위의 식은 재귀함수 연습 때 일종의 붕어빵 틀처럼 쓸 수 있는 기본 틀이 되므로, 잘 기억해야 한다.

2. 팩토리얼 구하기

recursive : n!=n*(n-1)!
base : 1!은 1
팩토리얼은 1부터 n까지의 곱으로 5!=1*2*3*4*5 이다.
팩토리얼이라는 용어를 썼지만 결국 위의 합 구하기와 원리는 같으면 합만 곱으로 바꾸면 된다.

function factorial(n){
  //base
  if(n<=1) return n; //1의 경우, 0의 경우를 합칠 수 있다.
  //recursive
  return n*factorial(n-1); 
}

3. n번째 피보나치 수열 구하기

recursive : n번째 값=(n-1)번째 값 + (n-2)번째 값
base : 2번째 값은 1, 1번째 값은 0
피보나치 수열은 0,1로 시작하여 그 전의 값과 그 전전의 값을 더해 다음 차례의 값이 오는 수열이다. 때문에 이 원리를 이용하면 재귀함수로 쉽게 n번째 피보나치 수열 값을 구할 수 있다.

function fibonacci(n){
  //base
  if(n===1) return 0;
  if(n===2) return 1;
  //recursive
  return fibonacci(n-1)+fibonacci(n-2); 
}

4. 배열의 모든 요소의 합 구하기

recursive : 첫번째 요소(머리)와 나머지(몸통)으로 분리
base : 더이상 몸통(의 개수)이 없을 때
요소들의 합 구하기, 곱 구하기 등등 recursive의 원리는 위에서봤듯이
요소 하나, 나머지 요소를 인자로 한 재귀함수
이렇게 나누어가는 패턴이다.
이를 쉽게 요약하면 머리(head)와 나머지 몸통(body)으로 나누는 것인데,
이 원리는 재귀함수를 풀 때 중요한 또 하나의 개념이다.
그냥 해결하는 것보다 머리, 몸통으로 나눠서 해결하는 것이 이후 문제들을 해결하는데 중요하다.

function sumArr(arr) {
  //의사코드
  //여기서 이 머리와 몸통은 변수로 선언해도 되고, 안해도 된다. 
  //let head=arr[0]
  //let body=arr.slice(1); ->head를 제외한 나머지 배열이 된다.
  
  //recursive case: arr[0]+재귀함수(arr.slice(1))
  //base case : 전달받은 배열의 길이가 0일 때

  // base case
  if (arr.length===0) {
    return 0;
  }

  // recursive case
  return arr[0]+arrSum(arr.slice(1));
}

5. 반복문 대신 재귀 함수 사용하기

recursive : 반복시 처리해야할 내용
base : 반복문이 멈출 조건
재귀함수를 효과적으로 연습하기 위해서는 반복문으로 풀 수 있는 문제를 재귀함수로 풀어보는 것이 좋다.
반복문을 사용하는 경우는 주로 배열이나 객체를 순회할 때이다.
반복문을 재귀함수를 처리하기 위해서 반복시 처리해야할 내용을 작성하고, 이 내용이 재귀함수 호출로 대체될 수 있도록 해야한다.
몇 가지 알아낸 팁은 다음과 같다.

• base case부터 생각하면 좀 더 쉽다.
• recursive case와 base case의 위치에 연연하지 않는다.

코드를 직접적으로 공개할 순 없기에 아래에 의사코드로 코드를 작성했다.

//아래의 함수는 객체를 순회하면서 작업을 처리해야 하는 함수이다.
//반복문을 사용해야 하는 경우는 주로 인자가 배열, 객체일 때이므로 
//인자를 배열로 받는 경우를 예로 들었다.
function 재귀함수(arr) {
  //머리와 몸통 구하기. 아예 안 써도 되고, 구조분해할당을 사용해도 된다.
  //머리를 하나씩 처리하면서 몸통을 재귀함수로 반복한다.
  //선언방법1
  let head = arr[0];
  let body = arr.slice(1);
  //선언방법2
  let [head, ...body]=arr;

  // base case : 반복문이 끝나는 조건
  if (arr.length === 0) {
    반복문이 끝날 때의 작업
  }

  //recursive case
  if (head와 관련된 조건1) {
    특수한 head에 대한 작업을 처리할 때 사용한다.
  }
  return 재귀함수(body);
}

6. 반복문 없이 순서가 뒤집힌 배열 리턴하기

핵심 : 재귀함수 호출시 배열은 변수에 나눠서 할당하고, 붙여서 전달한다.
이번 문제는 위의 5번처럼 반복문을 사용하되 1~4번처럼 문제를 쪼갤 수 없기에 어려웠다. 문제를 저렇게 단순하게 쪼갤 수 없다면 어떻게 해야할까?

• 무조건 쪼개기보다 먼저 처리해야할 값을 분리해보고
• 나머지를 최대한 재귀함수를 활용하는 방법으로 정리해보자.

순서가 뒤집힌 배열을 처리하는 과정을 아래처럼 차근차근 해보자.
가장 쉬운 방법은 빈 배열 result에 순서대로 앞에 추가하는 것이다.

ex) [1,2,3,4,5]
먼저 1을 빼서 빈 배열 result의 앞에 추가한다. -> [2,3,4,5],[1]
2를 빼서 result의 앞에 추가한다. -> [3,4,5],[2,1]
3을 빼서 result의 앞에 추가한다. -> [4,5],[3,2,1]
4을 빼서 result의 앞에 추가한다. -> [5],[4,3,2,1]
5를 빼서 result의 앞에 추가한다. -> [],[5,4,3,2,1]
그러면 더 이상 뺄 값이 없다.

여기까지는 base도 recursive case도 확실한데, 중요한 건 어떻게 result를 다음 재귀함수에 전달할 것인가?
둘 다 배열이기에 이어붙여서(concat) 리턴하면 된다.
재귀함수(나머지배열).concat(result)
[2,3,4,5],[1] -> [2,3,4,5,1]
이러면 나머지가 아니라 전체를 재귀함수에 전달하는 것 같지만,
각 단계를 잘 보면 매번 나머지만 재귀함수로 전달된다.

[2,3,4,5],[1] -> [2,3,4,5,1]
[3,4,5],[1,2] -> [3,4,5,1,2]
[4,5],[3,2,1] -> [4,5,3,2,1]
[5],[4,3,2,1] -> [5,4,3,2,1]

그렇게 해서 최종 리턴하는 형태도 결국 의도대록 뒤집힌 배열이 나온다.

아래는 이 과정을 담아낸 예제이며, 5번에서 언급한 head, body를 사용해 문제를 풀 수도 있다.

function reversedArr(arr) {
  //base
  if(arr.length===0) return [];
  //recursive
  let body=arr.slice(1);
  return reversedArr(body).concat(arr[0]);
}
//recursive case는 이렇게 바꿀수도 있다.
//let [head, ...body]=arr; 
//return resersedArr(body).concat(head);

7. 중첩된 배열의 요소 찾기

recursive : 재귀함수의 호출은 배열의 중첩도만큼 호출한다.
base : 배열이 1차원 배열인 경우
중첩된 요소를 찾을 때는 중첩된 횟수만큼 재귀함수를 호출하도록 문제를 풀어야 하는 것이 핵심이다. 이 경우에는 배열을 순회해야 하기 때문에 반복문을 사용한다.

1. 먼저 배열이 1차원 배열이라 가정하고 배열을 순회하며 원하는 요소를 찾는다.
2. 찾는 요소가 배열일 경우를 조건으로 추가하고,

• 그 배열 탐색의 결과를 변수에 할당하고
• 할당한 변수를 판별한다.

3. 찾는 요소가 없는 경우를 포함한 그 외의 경우를 처리한다.

function findArrValue(arr, value) {
  //1. base case : 1차원 배열 순회
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return true;
    } 
    //2. recursive case
    else if (Array.isArray(arr[i])) {
      let result = findArrValue(arr[i], value);
      if (result === true) {
        return true;
      }
    }
  }
  //3. 그 외의 값 처리
  return false;
}

위의 풀이는 아래처럼 재귀함수가 할당되는 변수의 선언 위치를 바꿀 수 있다.

// 다른 풀이 방법 1 - 재귀함수가 할당된 변수의 선언 위치가 바뀌었다.
function findArrValue(arr, value) {
  //1. base case : 1차원 배열 순회
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return true;
    } 
    //2. recursive case 분기
    else if (Array.isArray(arr[i])) {
      result = result.concat(arr[i]); //[...arr[i]]
    }
  }

  //2. recursive case 처리
  if (result.length > 0) {
    return findArrValue(result, value);
  }
  //3. 그 외의 경우 처리
  return false;
}

또한 아래처럼 reduce를 사용해볼 수도 있다.
여기서 중요한 건 위의 그 외의 경우인 false를 초기값으로 설정했고,
reduce의 누산기능 때문에 반복되는 것을 확인할 수 있다.
다만 주의할 점은 아래의 부분이다.
return findArrValue(curr, value) || acc;
논리곱은
false || false === false
true || true === true
true || false === true
false || true === true

function findArrValue(arr, value) {
  //1. base case : 1차원 배열 순회
  let result = arr.reduce((acc, curr) => {
    if (curr === value) {
      return true;
    }
    //2. recursive case
    else if (Array.isArray(curr)) {
      //중첩된 배열에 값이 있다면 여기서 true가 리턴된다.
      return findArrValue(curr, value) || acc;
    } else {
      //찾는 값이 있었다면 acc에는 true가 할당된다.
      //acc에 한 번 true가 할당되었다면 acc의 값은 계속 true가 되고
      //result에는 true가 할당된다.
      return acc;
    }
  }, false); //초기값인 false므로 acc의 기본값은 false가 된다.
  return result;
}

8. 다차원 배열 평탄화

핵심 : 평탄화는 flat=[].concat(arr) 구문을 사용한다.
recursive : 재귀함수의 호출은 배열의 중첩도만큼 호출한다.
base : 배열이 1차원 배열인 경우
7번과 같은 원리로 풀이하되 concat으로 평탄화하는 구문을 잘 숙지하고 있어야 한다. 이 평탄화 구문만 숙지하고 사용할 수 있다면 풀이 자체는 어렵지 않다.

function flatArr(arr) { 
  let result = [];
  //반복문을 사용해 각 배열의 요소가 배열인지 아닌지 확인
  for (let i = 0; i < arr.length; i++) {
    let flat;
    
    if (Array.isArray(arr[i])) {
      //recursive case - 다차원 배열 평탄화
      flat = flatArr(arr[i]);
    } else { 
      //base case - 1차원 배열 평탄화
      flat = arr[i];      
    }
    result = result.concat(flat); 
    //concat 대신 push와 스프레드 연산자를 사용할 수 있다.
    //ex) result.push(...flat);
    //다만 이 경우 result.push(...arr[i]); 는 안되니 공통으로 쓰지 않도록 주의한다.
  }
  return result;
}

위 문제는 head, body를 적용하여 아래처럼 풀 수도 있다.
주의할 점은 이 경우 위의 예제와 recursice case, base case가 다르다는 점이다.
recursive case는 body의 갯수만큼 재귀함수가 호출되고,
때문에 재귀함수가 호출될 수록 크기가 줄어든다.
따라서 base case는 빈 배열인 경우가 된다.

function flatArr(arr) {
  // base case
  if (arr.length === 0) {
    return [];
  }

  // recursive case
  const head = arr[0];
  const body = arr.slice(1);
  if (Array.isArray(head)) {
    return flatArr([...head, ...body]);
  } else {
    return [head].concat(flatArr(body));
  }
}

또한 reduce도 사용할 수 있다.

function flatArr(arr) {
  return arr.reduce(function (result, curr) {
    if (Array.isArray(curr)) {
      let flat = flatArr(curr);
      return [...result, ...flat];
    } else {
      return [...result, curr]
    }
  }, []);
}

---

노트 정리 후 느낀점

계속 공부하고, 과제하고, 코딩 문제풀다보니 전보다는 실력이 늘었긴 했다. 하지만 열심히 공부했다고 믿었던 것도 막상 활용하려니 파바밧!하고 떠오르진 않는 경험을 했다. 역시 복습이 정말로 중요하구나 깨닫는 기회가 되었다.
코딩문제 더 수월하게 푸는 그날까지!

이번의 부족한 점

• slice, concat은 기본적인 문법인데 바로 활용할 방법이 떠오르질 않았다.
• 문제를 쪼개는 건 할 수 있지만, 중간에 만족시켜야할 조건이 등장했을 때 재귀함수를 바로 사용하는 것이 힘들었다.

부족한 점 보완하기

• 주기적으로 정리했던 블로그 보기
• 관련 코딩문제 풀어보기
• 어려웠던 재귀함수 문제 한 번 더 풀어보기

오늘도 고생했다 나 자신😌