티스토리 뷰


4. 재귀 호출Recursion



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


음.. 저 예제들은 좀 복잡했다. 혼자 만들어봐야 할 것 같지만, 그냥 읽는 것으로... (어려운 것만 귀차니즘 발동인가.)

비재귀화하는 방법은 경우마다 다르다곤 하지만 공통점이 있다면 스택으로의 변수 저장과 처리작업의 선택이 관건이다.

즉, 함수 내부에서 루프를 이용해 함수역할을 구현할 때 변수요소만 적절히 바꿔주면 끝나는 것이다.

내가 그 정신에 입각해서 성능은 깡그리 무시해 버리고 형태를 유지한 채 그냥 비재귀화만 해보았다.

test.cpp

대충 만든거 (Inorder Insert하려고 큐 클래스를 사용하려다가 실패해서 난리가 났다;;)라 소스가 난장판이다. 어차피 읽을 필요도 없을 테니...

아주 억지스럽게도 while루프와 goto문가지고 재귀호출만 피했다 ㅋㅋ

물론 성능은 무진장 딸릴 거라 예상한다;;

근데, 함수 오버헤드 가지고 그렇게 비재귀화 고민하면 예제도 이미 push함수 하나로 최적화 물 건너간 게 아닐까...?

(push함수는 매크로 함수 같은 것으로 인라인화하면 해결 되긴 한다. 나름 가치는 있다.)


책은 EIP의 처리를 조건문만으로 한 것이고, 나는 switch goto문으로 한 것이 차이이다. 책이 복잡한 만큼 더 성능이 좋겠지.


나는 일반화의 방법을 따랐을 뿐이다.


나머지 예제는 그래픽쪽이 있는데 그건 구현 생략. 선 그리기와 프랙탈 그래픽에 재귀 호출이 쓰일 수 있다는 내용이다.


파일 탐색도 이미 함수 헤더가 dir.h, dos.h... 혼연C에 훌륭한 예제가 있으므로 차라리 그걸 보는 게 낫다.


댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
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
글 보관함