재귀란?
엘레베이터 거울처럼 거울 속의 거울 속의 거울처럼 자기자신을 반복하는 것입니다.
그리고 재귀 호출은 실행과정 중에 자기 자신을 호출하는 것입니다.
재귀는 언제 사용해야 하나요?
재귀는 다음과 같은 상황에서 아주 적합합니다.
1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
재귀적 사고 연습하기
1. 재귀 함수의 입력값과 출력값 정의하기 (재귀적 사고)
💭 이 문제는 재귀로 풀 수 있을 것 같아!
재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 됩니다. 재귀적으로 사고하는데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것입니다.
2. 문제를 쪼개고 경우의 수를 나누기 (잘개 쪼개어서 사고하는 법)
💭 base case랑 recursive case로 나눠야 되겠구나!
주어진 문제를 어떻게 쪼갤 것인지 고민합니다. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인합니다. 일반적인 경우, 입력값으로 이 기준을 정합니다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기입니다. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 됩니다. 그리고 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같다면, 문제를 제대로 구분한 것입니다.
3. 단순한 문제 해결하기 ( 탈출 조건)
💭 base case를 어떻게 세워야 할까?
문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)이라고 부릅니다.
재귀의 기초 단계(base case)는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성합니다.
4. 복잡한 문제 해결하기
💭 recursive case는 어떻게 세워야 할까?
남아있는 복잡한 경우 해결하기 그리고 함수 자신을 호출하기
recursive case(재귀 단계)는 반복되는 작업의 조건을 구성하는 것입니다.
자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
- 실생활에 사용되는 유용한 Tree 구조의 예시
- 폴더, 메뉴, DOM
- 자료 구조 중에 Tree 구조에 재귀 함수를 사용하는 이유
- 깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있기 때문
- 반복되는 작업을 재귀를 통해서 보다 간결하게 만들어서 효율성을 높일 수 있다
