재귀함수

Achievement Goals

Lesson - 재귀 함수

• 재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.
• 재귀를 언제 사용해야 하는지 알고 있다.
• 재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.
• 자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
  • 실생활에 사용되는 유용한 Tree 구조를 알고 있다.
  • 깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.

용어정리

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

• 재귀호출: 메서드 내에서 자기 자신을 반복적으로 호출하는 것

  • 재귀호출의 예: 팩토리얼(!), 제곱, 트리운행, 폴더목록표시 등등

재귀의 사용 시점

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

재귀적으로 사고하기

• 1. 재귀 함수의 입력값과 출력값 정의하기
• 2. 문제를 쪼개고 경우의 수를 나누기
• 3. 단순한 문제 해결하기
• 4. 복잡한 문제 해결하기
• 5. 코드 구현하기
     Bese Case / Recursive Case ( 잘 알아두기)

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

예시 문제

(1) 수(num)를 입력받아 1부터 num까지의 합을 리턴해야 합니다.

• 입출력 예시

let output = sumTo(10)
console.log(output);//555

• 코드

function sumTo(num) {
  if(num === 0){
    return 0
  }else{
    return num+sumTo(num-1)
  }
}

• 풀이
  num = 5 일 경우 // sumTo(5)
  첫 if문에서 벗어난다.
  그래서 return 값은 5+sumTo(4)가 된다.
  sumTo(4)가 되면, return 값은 4+sumTo(3)이 된다.
  sumTo(3)이 되면, return 값은 3+sumTo(2)이 된다.
  sumTo(2)이 되면, return 값은 2+sumTo(1)이 된다.
  sumTo(1)이 되면, return 값은 1+sumTo(0)이 된다.
  sumTo(0)은 0이다.
  그러므로
  sumTo(1)은 1이다.
  sumTo(2)는 3이다.
  sumTo(3)은 6이다.
  sumTo(4)은 10이다.
  결과적으로 sumTo(5)은 15이다.

• 결론
  재귀 적인 사고 !! 익숙해져야 할거 같다. 코드만 봐도 어떤식으로 재귀적으로 반복되는지 알수 있도록..