[CodeStates-Section3]U1.자료구조/알고리즘-재귀

1.후기

재귀함수를 배우면서 '이 좋은 걸 이제 알다니? 많이 써먹어야지' 했지만... 막상 쓰려고 하니 어려웠다. 부트캠프에서 내준 과제도 깔끔하게 풀리지 않았고 조건을 어떻게 나눠야 할지도 헷갈렸다. 코플릿을 여러 번 풀어봐야겠다.

2.새롭게 알게 된 것

Chapter1. 재귀의 이해
Chapter2. 재귀의 활용

<Chapter1. 재귀의 이해>

1.재귀의 개념

재귀: 원래의 자리로 되돌아가거나 되돌아옴
재귀 함수: 자기 자신을 호출하는 함수

2.재귀는 언제 사용하는 게 좋을까?

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

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있음. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉬움.

<Chapter2. 재귀의 활용>

1.재귀 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

2.재귀적으로 사고하기

-재귀 함수의 입력값과 출력값 정의하기
-문제를 쪼개기
-경우의 수를 나누기
-단순한 문제 해결하기
-복잡한 문제 해결하기

function fibonacci(num) {
  // 재귀 함수의 입력값과 출력값 정의하기: number -> number
  // 문제를 쪼개기 : fibonacci(5) -> fibonacci(3) + fibonacci(4)
  // 경우의 수를 나누기: num이 0인 경우, num이 1인 경우, 그 외
  // 단순한 문제 해결하기: num이 0인 경우 -> 0 반환, num이 1인 경우 -> 1 반환
  // 복잡한 문제 해결하기: fibonacci(num) -> fibonacci(num-2) + fibonacci(num-1)
  if(num <= 1) {
    return num
  }
  
  return fibonacci(num - 2) + fibonacci(num - 1)
}

<기타>

1.Array.prototype.flat()

const arr1 = [0, 1, 2, [[[3, 4]]]];
arr1.flat();// [0, 1, 2, 3, 4] -> 깊이가 1인 새로운 배열 생성(기본값 = 1)
arr1.flat(2);// [0, 1, 2, [3, 4]] -> 깊이가 2인 새로운 배열 생성

2.트리 찾기

1) 배열

2) 객체

3) DOM