재귀
함수가 스스로를 호출하는 것
재귀를 사용해야할 때
1.
주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2.
중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
재귀적 사고
1. 재귀 함수의 입력값과 출력값 정의
재귀 함수를 통해 도달하고자 하는 목표를 정의
2. 문제를 쪼개고 경우의 수를 나누기
문제를 쪼갤 기준을 정하고 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인
3. 단순한 문제 해결하기
문제를 여러 경우로 구분한 후 가장 해결하기 쉬운 문제부터 해결
4. 복잡한 문제 해결
남아있는 복잡한 경우 해결
5. 코드 구현하기
Base Case
재귀 호출에서 빠져나가기 위한 경우
Recursive Case
자신을 호출하는 함수를 포함한 경우
예시
Factorial
function factorial(n) {
if (n < 2) return 1;
return factorial(n - 1) * n;
}
JavaScript
복사
•
재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
•
꼬리 재귀 (tail recursion in js)
•
하노이의 탑 재귀 (js tower of hanoi in recursion)
•
조합 재귀함수 (js combination in recursion)