[TIL : 18] 자료구조 알고리즘 재귀

Achievement Goals : 재귀 함수

• 재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.

  yes!
  재귀란 실행 과정 안에서 자기 자신을 실행하는 것이다. 예를 들어,
  5! = 5*4*3*2*1 인 팩토리얼을 재귀로 호출하는 함수를 만들어 보았다.

  function factorial(num) {
    if (num === 1)
      return 1;
    return num * factorial(num - 1);
  }

• 재귀를 언제 사용해야 하는지 알고 있다.

  비슷한 방식으로 문제를 잘게 쪼갤 수 있거나, 중첩된 반복문이 많은 경우 사용하면 유용하다.
  위의 예시에서는 5! = 5*4! 5! = 5*4*3! ... 5! = 5*4*3*2*1이런 식으로 주어진 수에서 '-1'씩 한 값을 쪼개어 반복적으로 곱하는 함수를 간단하게 작성할 수 있다.

• 재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.

  base case : 재귀의 기초로 쪼개고 쪼개어 단순히 해결할 수 있는 결과값에 도달한 것이다. 탈출조건이 된다. 위의 예시로는 쪼개고 쪼개어 1을 만나면 return 1을 해주어 여태까지의 값을 곱해주는 것이다.
  recursive case : base case가 아닌 경우이다. 문제를 계속 쪼개어 나가는 동작을 말한다.

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