recursion

call stack

대부분의 프로그래밍 언어에는 함수의 호출 순서를 저장하는 자료 구조(data structure)가 구현되어있다. js에서 이는 call stack으로 불리며, 소스 코드에서 함수를 호출할 때 마다 stack에 그 정보가 쌓이고, 맨 꼭대기(top)에 쌓여있는 함수 호출 정보가 가장 먼저 삭제된다(pop).

재귀 함수를 호출하게 되면, 이 함수의 호출이 중단될 때 까지 call stack에 같은 재귀 함수가 여러개 쌓이게 된다. 그렇다면 재귀 함수란 무엇일까?

what is recursion?

a process(function) that call themselves from within their own code.

+) 재귀함수는 거의 모든 곳에 존재하며, JSON.stringify, JSON.parse와 같은 함수가 재귀 함수로 구현되어있다.

+) ??? 언제 loop를 쓰고, 언제 recursion을 써야하는지... 언제 어떤 방법을 쓰는게 더 나은 건지 감이 잘 안온다.

common problem of recursive solutions

1. maximum call srack size exceeded (=== stack overfolw)
   • 중단점이 없을 때(no base case) 
   • 중단점에 도달할 수 없을 때 
   • 중단점에 도달했으나, return 키워드가 없어 함수를 종료할 수 없을 때

example code here

다루는 내용

1. 재귀 함수 예시
   • count down function
   • factorial function
2. 재귀를 이용한 설계 패턴
   • helper method recursion
   • pure recursion
3. challenge 문제 풀기 
   • basic 
   • bonus