[JavaScript] 재귀

S3U1 W9D4 재귀 함수에 대해 배우는 날

Before learn...

• 자바스크립트 기초 문법

---

✅ TIL

• 재귀의 이해
• 재귀적으로 사고하기
• 재귀 문제 풀기

---

재귀 (recursion)

1️⃣ 재귀의 이해

재귀: 자기 자신을 호출하는 함수

function recursion () {
  console.log('hello');
  recursion();
};

자기 자신을 끝없이 호출하면서 body문이 계속해서 실행된다.

반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.
1. 문제를 가장 작은 단위로 쪼갠다.
2. 가장 작은 문제를 풀어서 전체 문제를 해결한다.

반복문도 재귀와 같은 일을 하지만,

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우

위와 같은 경우에 재귀를 사용하는 게 적합하다.

---

2️⃣ 재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기

문제를 가장 단순하게 정의한다.

2. 문제를 쪼개고 경우의 수를 나누기

문제를 어떻게 쪼갤 것인지 기준을 정한다.
입력값이나 문제의 순서와 크기로 문제를 구분한다.

문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.
입력값이 빈 배열인 경우, 그렇지 않은 경우 등

3. 단순한 문제 해결하기

: 재귀의 기초(base case)
문제를 더 이상 쪼갤 수 없는 경우 재귀의 탈출 조건을 구성한다.

4. 복잡한 문제 해결하기

recursive case
남아있는 복잡한 문제를 해결한다.

5. 코드 구현하기

function recursive(input1, input2, ...) {
  //base case
  if(문제를 더이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  
  //recursive case
  return 더 작은 문제로 새롭게 정의된 문제
}

---

문제 풀이 노트

base case를 먼저 생각하고
그 뒤에 recursive case를 생각한다.

Array.prototype.flat()

: 모든 하위 배열 요소를 지정한 깊이까지 재귀적으로 이어붙인 새로운 배열을 생성한다.

[1,2, ,4,5].flat()
>[1,2,4,5] //배열의 구멍도 제거한다.

const newArr = arr.flat([depth]) //depth = 중첩 배열 구조를 평탄화할 때 사용할 깊이 값

arr.flat() // 기본값 1
arr.flat(2) // 깊이 2만큼 평탄화
arr.flat(Infinity) // 모든 배열 평탄화

array.flat()을 재귀 함수로 구현해보는 문제

//입력: 다차원배열
//출력: 1차원 배열로 변환하여 리턴
//base case: 빈 배열은 빈 배열 result 리턴
//if (Array.isArray(arr[0]))이면 result.concat(flattenArr(arr[0])) 해준다. 
//또는 result.push(arr[0]) 해준다.

function flattenArr(arr) {
  let result = [];
  if(arr.length === 0) {
    return result;
  }
  for(let nums of arr) {
    if(Array.isArray(nums)) {
      result = result.concat(flattenArr(nums));
    }
    else{
      result.push(nums)
    }
  }
  return result;
}
//입력받은 배열의 요소를 반복문으로 하나씩 확인
//요소중에 배열이 있으면 풀어주기
//풀어진 배열 인자로 전달해서 재귀 호출

Array.prototype.concat()

: 배열 메소드이면서 배열을 인자로 받는다.
배열요소.concat(배열) 불가능!

---

디버깅

개발자 도구 콘솔창에 함수 입력
---> debugger; 함수(인자입력)
---> step f9
---> scope 확인
Call stack: 함수 실행 횟수 확인