[JS 알고리즘 - 재귀1] 재귀와 콜 스택 의 관련성 이해하기

아래 강의를 듣고 내용을 정리한 포스트 입니다.

https://www.udemy.com/course/best-javascript-data-structures/

JavaScript (JS) Algorithms and Data Structures Masterclass

 

재귀는 프로그래밍에서 솔루션 작성에 관한 새로운 사고 방식입니다. 이 글에서는 재귀에 대한 개념과 그 유용성을 이해하고, 재귀 함수 작성의 두 가지 핵심 구성 요소를 배울 것입니다. 또한, 콜 스택이라는 개념과 그것이 재귀와 어떤 관련이 있는지 알아봅니다.

재귀 함수란 무엇인가?

재귀 함수는 자기 자신을 호출하는 함수를 말합니다. 반복적인 방법 대신 재귀적 방법을 사용하여 문제에 대한 솔루션을 작성할 수 있습니다. 재귀 함수는 어떤 종료점(base case)에 도달할 때까지 더 작은 부분이나 변경되는 부분에서 반복적으로 수행합니다.

재귀 함수의 대표적인 예시:

• JSON.parse/JSON.stringify
• document.getElementById/DOM 순회 알고리즘
• Object 순회
• 데이터 구조를 직접 만들고, 트리나 그래프를 생성하고, 그것들을 순회하며 특정 요소를 검색할 경우 재귀가 포함될 때가 많습니다.

함수 호출과 콜 스택

거의 모든 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 있습니다.
JS에도 함수 호출을 관리하는 보이지 않는 일종의 데이터 구조가 존재합니다. 이를 콜 스택이라고 합니다.
콜 스택은 함수 호출을 관리하는 정적 데이터 구조입니다. 함수 호출 시 콜 스택의 꼭대기에 쌓이고, 함수가 끝나면 컴파일러가 스택의 제일 위 항목을 제거합니다.
함수 호출 시, 호출 스택의 꼭대기에 쌓이고, JS 컴파일러가 return문을 확인하거나 함수 안에 더 이상 실행할 코드가 없으면 스택의 제일 위에 있는 항목을 제거합니다. 
재귀 함수 사용 시 콜 스택은 계속해서 동일한 함수를 추가하게 되며, 언젠가는 종료 지점이 필요합니다.

재귀 함수 작성의 핵심 구성 요소

재귀 함수를 작성하려면 두 가지 핵심 구성 요소가 필요합니다.

• 종료 조건(base case): 재귀 함수가 언제 종료되어야 하는지를 결정하는 조건입니다.
• 자기 자신을 호출하는 부분: 함수가 자기 자신을 호출하며, 문제의 크기나 범위가 점차 줄어들게 됩니다.