[자료구조/알고리즘] 재귀

💡재귀함수

---

📌재귀의 이해 - 다르게 생각하기

• 어떤 문제를 해결할 때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법을 재귀(recursion)라고 한다

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

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

📌재귀적 사고 연습하기

재귀적으로 사고하기

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

function arrSum(arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  /*
  * Recursive Case : 그렇지 않은 경우
  * 문제를 더 이상 쪼갤 수 없는 경우
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
}

• 아래는 일반적인 재귀 함수의 템플릿이다.

function recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

📌factorial로 알아보는 재귀

function fac(n) {
  if(n === 1) {
    return 1;
  }
  return n * fac(n-1);
}

// 5! 을 예로 들자면
// 5! = 5 * 4 * 3 * 2 * 1 이므로, 5 * 4! 와 같다.
// 4! = 4 * 3 * 2 * 1 이므로, 4 * 3! 와 같다.
// 이와 같이 n * fac(n-1) 의 형태가 반복되어 나타나므로 재귀를 이용하기에 알맞다.
// 더 이상 쪼갤 수 없는 상태(n 이 1인 경우)가 되면 그 문제의 해답을 가지고 최종적으로 답을 찾게 된다.```