✏️Achievement Goals

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

📝summary

재귀함수 : 내가 나를 호출하는 함수
반복문과 호환이 되기 때문에 반복문으로 구현할 수 있으면 재귀함수로 구현 할 수 있다

반복문 대신 밑의 경우일때 재귀함수를 사용한다
1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
ex) tree구조에서 모든 노드의 값을 확인하는 경우 재귀를 사용하는 게 쉽고 코드의 가독성이 높다

재귀 함수를 작성할 때는 함수 내에서 다시 자신을 호출한 후
그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과
함수 종료 조건이 꼭 포함되어야 한다는 부분을 인지하고 작성하면 무한 루프를 방지할 수 있다

재귀함수 알고리즘

1. 1부터 100까지의 합

반복문 사용

let s = 0;
for(let i = 0; i < 100 i++){
  s += i;
}

s += 1
s += 2
s += 3
s += 4
...
s += 100 
// 5050

재귀함수 사용

function f(n){
  if(n <= 1){
    return 1
  }
  return n + f(n-1)
}
console.log(f(100)) // 5050

순번  f(n)     n    return        최종
1    f(100)  100   100 + f(99)   100+99+98+97...+2+1
2    f(99)    99   99  + f(98)   99+98+97...+2+1
3    f(98)    98   98  + f(97)   98+97+96...+2+1
...
2    f(2)      2    2  + f(1)    2+1
1    f(1)      1    1

반복문은 1부터 재귀는 100부터 시작한다
나를 호출해 나가면서 리턴값이 나를 호출하지 않을 때가 탈출 조건(재귀 호출이 멈추는 조건) 이다

일반적 재귀함수의 템플릿

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