Recursion(재귀 함수)

recursion의 핵심 :  recursion을 만들때는 탈출구부터 생각하라 !

대표적인 예) factorial, fibonacci

fibonacci 를 살펴보자

function fib(n){
  if(n === 0) return 0;        // 탈출구
  else if(n === 1) return 1;   // 탈출구
  else if(n > 1){
    return fib(n-1) + fib(n-2);  // 재귀
  }
} 

fib(6); // 8

- 리커전의 단점 :  호출횟수가 너무 많음,  성능상 손해임( 대안책(?) : 메모이제이션 )

- 리커전의 장점 : 표현방법에 있어서는 반복문보다 낫다

 

메모이제이션이란? 캐시를 구현한것이다 ( 한번 불려졌던건 기억해놓는다 그러므로 호출횟수가 훨씬 적어진다) 

---

다른 케이스들)

- 트리구조에서 ( 트리구조가 얼마나 깊을지 알 수 없기때문에 리커젼을 쓰면 효율적이다 ) 

1. 노드를 찾을때

2. JSON stringify

3. getElementsByClassName

---

Q. 그럼 반복문으로는 트리의 노드를 찾을 수 없을까?

A. 가능하다  ->  while문을 써서 찾는것이 가능하다

---

도전과제 : 유클리드 호제법 이용해서 최대공약수 리컬시브하게 구현하기