재귀는 매번 어렵다.
미루고 미뤄도 재귀는 찾아온ㄷr . . .☆
parents 노드부터 가장 깊은 child 노드까지 탐색을 하는 방법이다.
DFS의 그림이 그래프여서 JS에서도 그래프를 그려서 해야할 것 같지만, ' 재귀 ' 를 이용하여 편하게 풀이할 수 있다.
function DFS(x){
if(x===1) return;
else{
console.log(x);
DFS(x-1);
console.log(x+1);
}
}
DFS(4);
이런 함수를 실행했을 때, 어떤 출력 값이 나올까
스택에 담는다고 생각하면 편하다.
어디까지 실행했는지 고려하고, 스택 안에서 넣었다 뺐다 반복한다.
(함수를 선언할 때 스택이 만들어지는데, 스택 안에는 지역변수, 매개변수, 복귀주소가 들어있다.)
재귀에서는 언제 빠져나올지 고민하는 일이 가장 중요하다.
고려하지 않는다면 영원히 재귀가 깊어질 것이다.
예제 문제 |
자연수 N이 주어졌을 때 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하시오.
아직 실제로 적용하기엔 부족할 수 있어도,
기억하자 ! DFS = 적절히 멈출 곳이 어딘지 !