[인프런] 자바스크립트 알고리즘 문제풀이 입문 강의에서 재귀함수와 스택프레임에 대한 내용이 중요하고 어려워서 정리해본다.
내용 시작 전에 먼저 DFS(Depth-First Search: 깊이 우선탐색)와 BFS(Breadth-First Search: 너비 우선탐색)에 대해 간단한 이해를 돕는 영상을 보면 좋을 것 같다.
문제
자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.
- 입력설명
첫 번째 줄은 정수 N(3 <= N <= 10)이 입력된다. - 출력설명
첫째 줄에 출력한다. - 입력예제 1
3 - 출력예제 1
123
문제풀이
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n){
// DFS(깊이 우선탐색 함수), L(level)(이름 상관 없음)
function DFS(L){
if(L === 0) return; // 무한반복 막음 (DFS(0)이 되었을 때 종료)
else{
DFS(L-1); // 재귀함수(자기 자신 호출)
console.log(L);
// console.log(L)이 DFS(L-1) 앞에 나오면 3,2,1 을 출력하고 뒤에 나오면 1,2,3 출력한다.
}
}
DFS(n)
}
solution(3);
</script>
</body>
</html>
재귀함수
재귀함수란 함수가 자기 자신을 호출하는 것을 말한다. 반복된다는 면에서 for 문과 유사하다. 하지만 for 문은 for 문이 완료되고 나면 자료구조(ex. stack)에 저장하지 않는 이상 이전 수행 코드의 정보를 사용할 수 없다. 재귀함수를 쓰면 운영체제가 스택 메모리에 정보를 저장해두기 때문에 개발자가 따로 자료구조를 구현하지 않아도 된다.
재귀함수는 '스택' 자료구조 원리를 사용하기 때문에 위와 같은 흐름으로 쌓이고, 다시 위에서부터 제거되며 대기하고 있는 13라인의 console.log(L)을 순차적으로 실행한다. (즉, console.log(L)의 위치에 따라 재귀를 먼저 작동하는 여부가 결정되어 함수가 실행되는 것으로 이해하면 될 것 같다.) console.log(L)가 여기서 쓰인 12라인의 재귀함수 DFS(L-1) 이전에 나오면 대기 없이 출력 후 재귀함수가 작동되기 때문에 결과값은 3, 2, 1 이고 위의 케이스는 1, 2, 3이 나오는 것이다.
스택 프레임의 구조 및 동작 원리를 이해하고 이후 잘 활용해보자! for문 대신 재귀함수로 구현할 때 편리한 점에 대해서 설명한 @그냥노깡님의 블로그 글도 참고해보면 도움이 된다. 재귀함수의 이점을 한 마디로 정리하자면, stack을 별도로 만들어서 저장해 사용해야 하는 for문 방식을 쓰지 않고 간단하게 구현할 수 있다는 점.
'JavaScript' 카테고리의 다른 글
| [JavaScript] 얕은 복사(Shallow copy)와 깊은 복사(Deep copy) (0) | 2023.09.20 |
|---|---|
| [JavaScript] == 와 === 의 차이 (0) | 2023.09.19 |
| [JavaScript] RegExp 정규표현식 (1) | 2023.07.12 |
| [JavaScript] 최대공약수(GCD) & 최소공배수(LCM) 구하기 (0) | 2023.07.11 |
| [JavaScript] 배열 splice 메서드 (0) | 2023.07.09 |
