재귀

학습 목표

• 재귀함수 작성의 두 가지 핵심 구성 요소 이해하기
• 호출 스택
• 호출스택과 재귀와의 상관관계
• 재귀함수 호출 디버깅 하기
• 헬 퍼 메소드와 순수 재귀 비교하기

재귀의 정의

자기 자신을 호출하는 것.

재귀가 중요한 이유

• 이미 자바스크립트엔진에서 많이 사용하고 있음
  • JSON.parse, JSON.stringify 도 재귀함수다.
  • document.getElementById and DOM 순회 알고리즘
  • 객체 순회

콜스택 이해하기

• 거의 모든 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 있다.
• 호출된 함수는 다른 함수가 반환될 때까지 기다리는 경우가 많다.
• 함수가 올바른 순서대로 호출되는 것을 담당하는 데이터구조가 바로 콜스택(호출스택)이다.

재귀 전략

• 기본 개념: 동일한 함수를 게속 호출하면서, 하나의 함수가 자기 자신을 재귀적으로 호출하게 한다.
• 중단점이 있어야한다. (종료조건 = 재귀가 멈추는 시점)
• 두 번째 기본요소 중 첫번째는 라인을 끝내는 종료 조건, 두 번째는 다른 입력값. (매번 들어가는 다른 데이터를 의미)

헬퍼 메소드 재귀

• 두 개의 함수가 존재한다. (하나는 자기 자신을 호출하는 함수, 다른 하나는 그 함수를 호출하는 함수)
• 데이터를 배열이나 객체 등에 저장해야할 때, 바깥 함수에서 결과값을 선언하고, 재귀 함수의 결과값을 결과값에 담는 방식

순수 재귀

• 배열을 사용하고 헬퍼 메소드 없이 순수 재귀 솔루션을 작성하는 경우, 배열을 복사하는 slice, spread 연산자, concat 같은 메소드를 사용할 수 있으며 , 배열을 변경할 필요가 없다.
• 문자열은 변경할 수 없기때문에, slice 나 substring 을 사용해서 사본을 만들어야한다.
• 객체의 경우, Object.assign 이나 spread 연산자를 사용하기