[ALGORITHM]recursion

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

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

function recursion() {
  console.log("recursion!");
  recursion();
}

재귀로 문제 풀기

문제를 작게 쪼갠다. => 더 작아지지 않을 때 까지. => 가장 작은 단위의 문제를 해결함으로 전체문제 해결

자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 arrSum 을 작성

function arrSum(arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  // 안적으면 무한으로 호출해벌임
  if (arr.length === 0) {
    return 0;
  }
  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
  return arr.shift() + arrSum(arr);
}

재귀 사용 상황

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

모든 재귀는 반복문으로 해결할 수 있음을 명심

---

재귀적으로 사고

1. 재귀 함수의 입력값과 출력값 정의하기
2. 문제를 쪼개고 경우의 수를 나누기
3. 단순한 문제 해결하기 - 재귀 탈출조건
4. 복잡한 문제 해결하기
5. 코드 구현하기

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }

  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}

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

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

5! = 5(4321) 4! = (432*1) …

function fac(n) {
  // n이 4라면
  if (n === 1) return 1;

  return n * fac(n - 1); // fac(3)이 호출 그 안에서 fac(2)가 호출 그 안에서 fac(1)이 호출
}

재귀 피보나치

function fibonacci(num) {
  if (num === 0) return 0;
  if (num === 1) return 1;

  return fibonacci(num - 2) + fibonacci(num - 1);
}