DFS에서 재귀를 사용하는 방법 vs 스택을 사용하는 방법 

    
DFS에서 재귀를 사용하는 방법 vs 스택을 사용하는 방법

DFS(Depth-First Search)에서 **재귀를 사용하는 방법**과 **스택을 사용하는 방법**은 사실상 같은 논리를 구현하지만, 사용하는 스택의 종류가 다를 뿐이에요:

1. **재귀를 사용하는 DFS**:  
   재귀 호출은 시스템 스택을 이용해 함수 호출 정보를 저장해요. 이 경우, 재귀 함수가 호출될 때마다 시스템 스택에 함수 호출이 쌓이고, 함수가 종료되면 스택에서 빠져나가는 방식으로 동작해요. 즉, **시스템의 호출 스택(Call Stack)**을 직접 이용하는 거죠.

2. **스택을 사용하는 DFS**:  
   이 방법은 명시적으로 `stack` 자료구조를 사용하여 구현해요. 우리가 직접 스택을 선언하고, 노드를 추가(push)하고 제거(pop)하면서 DFS를 수행하는 거예요. 재귀 없이 반복문(while)을 사용하여 스택이 빌 때까지 탐색을 진행하죠.

정리하자면, **재귀 DFS는 시스템 스택을 사용하는 DFS**이고, **명시적 스택을 사용하는 DFS는 우리가 직접 관리하는 스택을 사용하는 DFS**라는 차이가 있을 뿐, 알고리즘의 동작 방식은 동일합니다.

두 방법의 차이점으로는 다음이 있어요:

- **시스템 스택(재귀)**은 깊이가 깊어질수록 스택 오버플로우(Stack Overflow) 위험이 커질 수 있어요. 보통 C/C++ 같은 언어에서는 재귀 깊이가 수천~수만 이상이 되면 스택 오버플로우를 발생시킬 수 있죠.
- **명시적 스택**을 사용하면 스택 크기를 코드에서 제어할 수 있기 때문에, 매우 깊은 트리 구조에서도 상대적으로 안전하게 사용할 수 있어요.

따라서, **스택의 크기와 깊이가 중요한 문제**에서는 재귀보다 명시적 스택을 사용하는 것이 더 안전할 수 있습니다.

## 재귀는 항상 지양해야 하나?
그렇다고 재귀를 무조건 피할 필요는 없어요. 상황에 따라 재귀와 명시적 스택(반복문) 중 어떤 것을 사용할지는 적절하게 판단하는 것이 중요해요. 각각의 장단점이 있어서 문제의 특성과 코드의 가독성, 유지보수성을 고려해야 해요.

### 재귀를 사용해도 좋은 경우
1. **문제의 깊이가 깊지 않을 때**:
   - 재귀 깊이가 크게 깊어지지 않는 경우, 재귀를 사용해도 문제가 없어요. 예를 들어, 트리 탐색에서 깊이가 100 정도라면 대부분의 환경에서 재귀로도 무리 없이 동작해요.
   
2. **코드의 가독성이 중요할 때**:
   - 재귀는 자연스럽게 함수 호출로 표현되기 때문에 코드가 간결하고 읽기 쉬운 경우가 많아요. 예를 들어, 이진 트리의 중위순회(Inorder Traversal) 같은 경우는 재귀로 작성하면 훨씬 직관적이에요.

3. **재귀적 사고가 편리한 문제**:
   - 어떤 문제는 본질적으로 재귀적 정의를 가지고 있어요. 예를 들어, 피보나치 수열, 분할 정복(Divide and Conquer) 알고리즘, 백트래킹(Backtracking) 문제 등은 재귀적 사고로 접근하는 것이 자연스러워요.

### 재귀 대신 반복문(명시적 스택)을 사용해야 할 때
1. **깊이가 매우 깊어질 가능성이 있는 경우**:
   - 예를 들어, DFS를 사용할 때 그래프의 깊이가 수천~수만 이상으로 커질 가능성이 있다면, 재귀 대신 반복문을 이용한 스택 기반 DFS가 안전해요. 재귀 호출이 너무 깊어지면 스택 오버플로우로 프로그램이 비정상 종료될 수 있어요.

2. **제한된 시스템 환경에서 메모리 사용을 줄여야 할 때**:
   - 재귀 호출은 시스템 스택을 이용하기 때문에, 반복문을 이용한 스택 기반 접근보다 메모리 사용이 더 클 수 있어요. 제한된 메모리 환경에서는 반복문을 이용해 명시적으로 스택을 관리하는 편이 더 효율적일 수 있습니다.

3. **시간 복잡도를 최적화할 때**:
   - 반복문과 명시적 스택을 이용한 DFS는 재귀 호출에 비해 함수 호출 오버헤드가 없어서 약간의 성능 차이가 있을 수 있어요. 이런 미세한 최적화가 중요한 경우 반복문을 선호하는 것이 좋습니다.

### 결론
- **작고 간단한 문제**, **재귀적 사고가 자연스러운 문제**에서는 재귀를 사용해도 좋아요.
- **깊이가 깊어질 가능성이 있는 문제**, **제한된 환경에서의 성능 및 메모리 최적화가 필요한 문제**에서는 반복문과 명시적 스택을 사용하는 것이 더 좋습니다.

결국, **재귀와 반복문(명시적 스택) 모두 장단점이 있으므로 문제 상황에 따라 적절히 선택**하는 것이 중요해요. 재귀가 때로는 더 직관적이고 간결한 코드를 만들 수 있기 때문에, 깊이가 너무 깊어질 위험만 없다면 가독성을 위해 재귀를 사용하는 것도 좋은 선택이 될 수 있습니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

js 스트링에서 요소 갯수 세기

이상하다 https://stackoverflow.com/questions/881085/count-the-number-of-occurrences-of-a-character-in-a-string-in-javascript If you're looking for the commas: (mainStr. split ( "," ). length - 1 ) //3 If you're looking for the str (mainStr. split ( "str" ). length - 1 ) //4   console . log (( "str1,str2,str3,str4" . match ( /,/g ) || []). length ); //logs 3 console . log (( "str1,str2,str3,str4" . match ( new RegExp ( "str" , "g" )) || []). length ); //logs 4
Read more »

STUDY

@GetMapping("/proxy-download") public ResponseEntity<Resource> proxyDownload() {     String sourceUrl = "https://example.com/file-to-download.bin";     ResponseEntity<byte[]> response = restTemplate.exchange(         sourceUrl,         HttpMethod.GET,         null,         byte[].class     );     byte[] fileBytes = response.getBody();     // 👉 원본 Content-Disposition 헤더에서 파일 이름 추출     String disposition = response.getHeaders().getFirst(HttpHeaders.CONTENT_DISPOSITION);     String filename = "default.bin"; // fallback     if (disposition != null && disposition.contains("filename=")) {         // Content-Disposition: attachment; filename="some_file.bin"         filename = disposition.split("filename=")[1].replace("\"", "").trim();     }     HttpHeaders ...
Read more »

javascript cheatsheet

JavaScript 기능들을 정리한 치트시트를 제공합니다. 이 치트시트는 데이터 구조와 알고리즘을 구현하는 데 필요한 기본적인 구문과 기능을 포함하고 있습니다. ## JavaScript Coding Cheat Sheet ### 1. **기본 문법** #### 변수 선언 ```javascript let variable = value;   // 변수 선언 (변경 가능) const constant = value; // 상수 선언 (변경 불가) ``` #### 함수 선언 ```javascript // 함수 선언식 function functionName(params) {   // 함수 내용 } // 함수 표현식 const functionName = function(params) {   // 함수 내용 }; // 화살표 함수 const functionName = (params) => {   // 함수 내용 }; ``` ### 2. **기본 데이터 구조** #### 배열 (Array) ```javascript let arr = [1, 2, 3]; // 배열 길이 console.log(arr.length); // 배열 요소 접근 console.log(arr[0]); // 배열의 끝에 추가 arr.push(4); // 배열의 끝에서 제거 arr.pop(); // 배열의 앞에 추가 arr.unshift(0); // 배열의 앞에서 제거 arr.shift(); ``` #### 객체 (Object) ```javascript let obj = {   key1: 'value1',   key2: 'value2' }; // 속성 접근 console.log(obj.key1); // 속성 추가 또는 변경 obj.key3 = 'value3'; // 속성 제거 delete obj.key2; ``` ### 3. **반복문 및 조건문** #### 반복문 ```javascript // for 반복문 for (let i = 0; i ...
Read more »