그럼 재귀는 언제 써야할까?
(1) 주어진 상황이 구조는 비슷, 더 작은 문제로 나뉘어 질 수 있는 경우
그럼
for나whileloop를 쓰지?
=> 때로는Tree 탐색같이 재귀를 쓰면 편한 경우도 있기 때문에 상황에 맞게 맞춰 써야겠다.
(2) 중첩된 루프가 많거나 중첩의 정도를 알 수 없는 경우
재귀를 쪼개는 법
(1) 무엇을 입력받고, 무엇을 리턴해야 하는지 목표를 정한다.
=> 이를테면, "Array를 받아서 number를 리턴한다" 같이 => Fn([Array]) => number
(2) 입력받은 값을 기준으로 생각.
- 입력받은 값을 하나씩 떼어서 쪼갤 수 있는가?
- 입력받은 값에 어떤 순서를 정할 수 있는가?
- 만약 가능하다면, 경우의 수를 생각, 언제까지가 떼어내어 계산할 수 있고, 뗴어내지 못하는 순간은 언제인가.
해서, 결국 결론은 1편의 결론과 같다.
(1) Base Case setting
(2) Recursive Case Setting
(3) Base Case에 걸리냐? 아니면 Recursive Case 실행 다만 실행할 때, Recursive Case에 들어가는 인풋에 변화를 주어서 실행해야 겠지(Base 케이스에 가까워 지도록)
처음 호출을 포함한 중첩 호출의 최대 개수를 재귀의 깊(Recirsion Depth)이라고 함. 자바 스크립트는 대략 만개까지 허용(확인 필요.)
재귀의 깊이는 결국 콜 스택에 들어가는 실행 컨텍스트 수의 최대값과 같다.
실행 컨텍스트는 메모리를 차지하므로 재귀를 사용할 때는 메모리 요구사항에 유의해야 한다. n을 늘리면 n이 줄어들 때마다 만들어지는 n개의 실행 컨텍스트가 저장될 메모리 공간이 필요하기 때문이다.
반복문이 오히려 메모리가 더 절약 됨.
recursive traversal
재귀적 순회를 구현할 때 재귀를 사용하면 좋다.
