TIL이 아니라 점점 YIL이 되어가는 건 기분 탓 이겠지..?
재귀
원래의 자리로 되돌아온다.
JS에선? 스스로를 호출하는 함수
언제써?
두 문제가 있을 때 크기만 다를뿐 문제를 푸는 방법(로직)이 같은면 쓴다.
문제가 얼마나 중첩이 되었는지 모를 때 쓴다. *반복문을 무한으로 쓸 수 없기 때문
어떻게 써?
1. 재귀를 사용해야 하는 문제인지 파악한다. (언제써? 확인)
2. 함수에 입력받는 값과 출력되는 값을 파악한다. (ex. boolean타입 리턴 => 비교 연산자 써야겠다)
3. base case랑 recursive case를 구분하는 기준을 파악한다. (쪼개기)
4. Base Case를 찾는다. *내생각엔 이 부분이 가장 중요하다
함수가 재귀되어 다시 실행되었을 때 조건을 나누어 어떤 값을 리턴하거나 패스해야하는지 적어야한다.
5. 최종적으로 리턴받고 싶은 식을 파악하고 리턴받는다.
쪼개기
풀고자 하는 문제가 아주 간단해질 때 까지(바로 풀릴 때 까지) 반복해서 쪼개준다.
ex) [1, 2, 3, 4] 배열을 전부 더하고 싶다면
1. 1에 2와 3, 4를 더해준 값을 더해주면 된다
2. 2, 3, 4의 합은 2에 3과 4를 더해준 값을 더해주면 된다
3. 3, 4의 합은 3에 4와 아무것도 더해주지 않은 값을 더해주면 된다
4. 4의 모든 합은 4이다 => 문제 바로 해결
5. 3번으로 재귀해서 최종식(더하기) 진행
6. 2번으로 재귀..
7. 1번으로 재귀..
8. 배열[1, 2, 3, 4]의 모든 요소의 합을 구할 수 있다
이렇게 비효율적인 계산을 왜하지?
지금은 문제가 간단했지만 10차원 배열, 객체안의 객체안의 객체안의 객체의 값을 찾고자 할 땐?
얼마나 반복되는지 몰라서 원하는 값이 나올때까지 반복문을 돌려야 할 땐?
재귀에서 가장 중요하다고 생각되는 부분은
- 함수를 어떻게 재귀 시킬 것 인가 (func(arr.slice(1)), func(obj.obj)..etc)
- 재귀된 함수를 통해 어떠한 상황에서 어떤 값을 리턴할 것 인가 (계속 재귀시킬거야?, 끝낼거야?)
