TIL-211109

재귀함수

• 재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.
  • 함수를 스스로 호출하는 것, 대표적 예시: factorial(n!)
  • 5! = 5 4! = 5 4 3!....5 4 3 2!
  • n! = n * (n-1)! (n===2가 될때까지, 1!, 0!은 1임)

function factorial(n) {
  // base case, n이 0이면 재귀를 끝낸다
  if (n===0) {return 1;}
  // recursive case, n이 0이 아니면 계속 재귀한다
  return n * factorial(n - 1);}

• 또 다른 예시: fibonacci 수열, tree search(tree object, DOM element)
• 재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.

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

• 자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
  • 실생활에 사용되는 유용한 Tree 구조를 알고 있다.
  • 깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.
• 재귀의 장점: 알고리즘이 재귀로 표현하기에 좋은 경우, 가독성이 좋아진다
• 재귀의 단점: 리턴될 때까지 call stack을 새로 생성하는 구조라, 메모리 사용량이 크다