티스토리 뷰
재귀 함수란?
함수가 직접 또는 간접적으로 자신을 호출하는 프로세스를 재귀함수라고 합니다
재귀 알고리즘을 이용하면 복잡한 문제들도 간단하게 해결할 수 있습니다
반복문도 마찬가지지만 재귀함수도 종료지점을 제대로 생각하지 않고 구현을 하면 스택 오버 플로우가 발생할 수 있으니 항시 주의해서 구현을 해줘야합니다.
재귀 함수 예제
function solution(n) {
function DFS(L) {
if (L === 0) return;
else {
console.log(L);
DFS(L - 1);
}
}
DFS(n);
}
console.log(solution(3));
반대로 콘솔로그를 DFS 밑에 위치시키게 된다면
function solution(n) {
function DFS(L) {
if (L === 0) return;
else {
DFS(L - 1);
console.log(L);
}
}
DFS(n);
}
console.log(solution(3));
이러한 이유를 알기 위해서는 스택에 대하여 알아야 합니다.
스택이란?
- 메모리의 스택 영역은 함수의 호출과 관계되는 지역변수, 매개변수, 리턴 값등의 임시데이터를 저장합니다.
- 스택이란 단어는 ‘차곡 차곡 쌓여진 더미’를 의미합니다.
- LIFO(Last In First Out, 후입선출) 구조라고도 합니다.
이러한 스택의 정보에는 매개변수 L, 지역변수 , 복귀 주소 등 다양한 정보들이 담겨 있는데요.
여기에서 재귀 함수가 실행 될 때
function solution(n) {
function DFS(L) {
if (L === 0) return;
else {
DFS(L - 1);
console.log(L);
}
}
DFS(n);
}
console.log(solution(3));
스택이 쌓인 것마다 자신이 어디에서 호출되었는지 정보를 가지고 하나씩 빠져나와서 다시 자신이 진행했던 곳을 기억하고 그 이후로부터 진행하는 방식입니다.
알고리즘을 푸는 데 재귀함수를 이용한 DFS 나 BFS를 잘 사용하고 싶어서 공부하게 되었습니다.
'알고리즘' 카테고리의 다른 글
이진 트리 넓이 우선 탐색(BFS) 이란 // 큐(Queue)란 (0) | 2022.03.25 |
---|---|
이진트리 순회(깊이우선탐색) DFS , 전위순회 , 중위순회 , 후위순회 (0) | 2022.03.24 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 북클럽
- nextjs
- Storybook
- 윤성우 열혈C프로그래밍
- NextRequest
- WSL2
- electron
- 프리온보딩
- 우아한테크코스
- 노마드코더
- 스토리 북
- 원티드
- C언어
- CLASS
- import/order
- jest
- React
- 노개북
- error
- 아차산
- createPortal
- TopLayer
- javascript
- 초보
- 위코드
- nodejs
- 프론트앤드
- NextApiRequest
- env
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
글 보관함