티스토리 뷰
1. 재귀호출 서론 |
유의점
1. 물론 종료조건이 없으면 안 된다.
2. 상호 호출해서 1의 상황을 일으켜도 안 된다.
전략
1. 문제의 크기를 조금씩 줄여가는 방법. 문제의 크기가 점진적으로 줄어드는 점에서 두번째 유형과 다르다.
2. 문제의 크기를 양분하여 가는 방법. 꼭 절반이 아니어도 되며(퀵 정렬) devide and qunquer라고도 부른다.
3. 문제 자체에 점근하여 가는 방법. 트리에서 노드를 찾아갈 때 한번에 찾을 순 없다.
... 근데 난 왜 잘 구분이 안 가지. 특히 1, 2번.
예제로는 누승factorial 구하기, 피보나치 수열 구하기, 하노이의 탑이 나왔다.
2. 재귀함수를 비재귀함수로 바꾸기 |
비재귀함수로 바꿔야 하는 걸까? 이유는 함수를 부를 때마다 오버헤드, 즉 지연이 생기기 때문이다.
어차피 함수는 스택에 의해 구현되는 것에 불과하기에 이론적으로 모두 비재귀로 바꿀 수 있을 듯 하다. 스택만 구현해주면 되므로. 더 빨라지는지에 대한 문제를 제껴두면.
이 책에서는 스택을 하나만 준비해서 비재귀 함수로 변환하는 방법을 알려주었다.
재귀호출이 하나인 경우 - factorial예제
재귀호출이 둘인 경우 작업 선행 - tree preorder traverse
재귀호출이 둘인 경우 작업 중간에 - tree inorder traverse, hanoi
재귀호출이 둘인 경우 작업 마지막 - tree postorder traverse
음.. 저 예제들은 좀 복잡했다. 혼자 만들어봐야 할 것 같지만, 그냥 읽는 것으로... (어려운 것만 귀차니즘 발동인가.)
비재귀화하는 방법은 경우마다 다르다곤 하지만 공통점이 있다면 스택으로의 변수 저장과 처리작업의 선택이 관건이다.
즉, 함수 내부에서 루프를 이용해 함수역할을 구현할 때 변수요소만 적절히 바꿔주면 끝나는 것이다.
내가 그 정신에 입각해서 성능은 깡그리 무시해 버리고 형태를 유지한 채 그냥 비재귀화만 해보았다.
대충 만든거 (Inorder Insert하려고 큐 클래스를 사용하려다가 실패해서 난리가 났다;;)라 소스가 난장판이다. 어차피 읽을 필요도 없을 테니...
아주 억지스럽게도 while루프와 goto문가지고 재귀호출만 피했다 ㅋㅋ
물론 성능은 무진장 딸릴 거라 예상한다;;
근데, 함수 오버헤드 가지고 그렇게 비재귀화 고민하면 예제도 이미 push함수 하나로 최적화 물 건너간 게 아닐까...?
(push함수는 매크로 함수 같은 것으로 인라인화하면 해결 되긴 한다. 나름 가치는 있다.)
책은 EIP의 처리를 조건문만으로 한 것이고, 나는 switch goto문으로 한 것이 차이이다. 책이 복잡한 만큼 더 성능이 좋겠지.
나는 일반화의 방법을 따랐을 뿐이다.
나머지 예제는 그래픽쪽이 있는데 그건 구현 생략. 선 그리기와 프랙탈 그래픽에 재귀 호출이 쓰일 수 있다는 내용이다.
파일 탐색도 이미 함수 헤더가 dir.h, dos.h... 혼연C에 훌륭한 예제가 있으므로 차라리 그걸 보는 게 낫다.
'지식저장소 > 읽은 책 요약' 카테고리의 다른 글
C로 배우는 알고리즘 - 복습 겸 요약 7 (0) | 2012.11.22 |
---|---|
C로 배우는 알고리즘 - 복습 겸 요약 6 (0) | 2012.11.20 |
C로 배우는 알고리즘 - 복습 겸 요약 4 (0) | 2012.11.17 |
C로 배우는 알고리즘 - 복습 겸 요약 3 (0) | 2012.11.14 |
C로 배우는 알고리즘 - 복습 겸 요약 2 (0) | 2012.11.13 |
- Total
- Today
- Yesterday
- Windows Defender
- MSVC 2017 RC
- Authentication
- Qt5
- Rust
- getch()
- MSVC
- SHAREX
- WSL
- React
- Kotlin
- Haskell
- coroutine
- CLion
- game design
- novel review
- C/C++
- MSVC2013
- software compraison
- hooks
- IntelliJ
- intellisense
- Notion
- V3 Lite
- gram
- error highlighting
- JWT
- Deemo
- Code Snippet
- C++11
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |