Lisp 에서 tail recursion 질문입니다.
글쓴이: azura4 / 작성시간: 일, 2007/01/07 - 8:56오후
on Lisp를 읽고 있는 Lisp 초보입니다.
이 책 초반부에 소개된 유틸리티 함수 중,
flatten 이라는 함수의 구현이 tail recursion 인지 잘 이해가 안됩니다.
;구현
(defun flatten (lst)
..(labels ((rec (x acc)
............(cond ((null x) acc))
..................((atom x) (cons x acc))
..................(t (rec (car x) (rec (cdr x) acc))))))
....(rec lst nil)))
;실행 예
CL-UESR> (flatten '(a (b c) ((d e) f)))
(A B C D E F)
이 함수의 구현을 보면 rec의 인자 x가 nil 이나 atom이 아닐 경우 rec를 호출하면서 두번째 인자값으로
또 다른 rec 호출의 리턴값을 사용하고 있는데요, 이렇게 하면 그때마다 어디서 rec를 호출하는지 스택에
기록되는것 아닌가요? 글로 써놓고 보니 질문이 좀 엉성하네요. ㅡㅡ; 저는 재귀호출의 리턴값을 사용하지
않는 것이 tail recursion 인것으로 이해하고 있었는데요, 혼란스럽네요. 책에 보면 tail recursion인
것처럼 나오거든요.
이 구현이 tail recursion 이 맞는지, 어떻게 그렇게 이해할 수 있는지 조언 부탁드립니다. 꾸벅
(들여쓰기가 안되서 점으로... ㅡㅡ;)
Forums:
LISP 을 모르다 보니...
Tail recursion 을 모르는 것은 아닙니다만 단지 반환값의 사용여부만 가지고 판단할 수는 없습니다.
물론 번역기가 반복형식으로 전환하기는 어렵겠습니다만 흔히 작성되는 계승함수는
반환값을 사용합니다만 꼬리재귀라고 볼 수 있다고 생각합니다.
이 경우는 진입을 할 때 아무런 작업없이 진입을 하니까 가능하겠죠.
즉 진입전에만 작업하거나 혹은 탈출 후에만 작업이 이루어진다면 비대칭으로서 꼬리재귀라고 생각합니다.
또한 역시 흔히 작성되는 Quick Sort 의 경우 반환값을 사용하지 않습니다만 꼬리재귀라고 말할 수 없겠죠.
안쪽 (rec ...)이 아닌
안쪽 (rec ...)이 아닌 바깥쪽 (rec ...)만 보면, 끝난 다음 따로 할 일이 없기 때문에 tail recursion이 맞습니다. 그런데, 안쪽 (rec ...)이 있기 때문에, 전형적인? tail recursion이라 보기는 무리가 있습니다. 절반쯤 tail recursion이라 할 수 있을 것 같습니다.
간단히 tail recursion이냐 아니냐를 따지기는 힘들 것 같군요. 대신 p.23에 나온 것처럼 accumulator를 썻기 때문에 그나마 좀 속도면에서 다른 방식을 쓴 것보다 빠를 것으로 예상할 수 있습니다.
그리고, 아직 LISP에 대해 잘 모르신다면, On Lisp을 보는 것은 좀 무리가 있습니다. 꽤 어렵거든요. 차라리 같은 저자가 쓴 ANSI Common LISP을 보시는 것이 나을 것 같군요.
--
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Korean Ver: http://www.cinsk.org/cfaqs/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Korean Ver: http://cinsk.github.io/cfaqs/
practical common lisp도
practical common lisp도 졸트어워드에 빛나는 좋은 책이더군요! 물론 웹에서 볼 수 있음
http://www.gigamonkeys.com/book/
--
콘쏠의힘
--
Life is short. damn short...
답변 감사합니다.
이전에 C++ 쓸 때는 거의 쓰지 않아서 그런지 recursion에 익숙하지 않아서...
진도가 잘 안나가네요 휴..
그리고 책 추천 감사합니다. 좋은 책이어서 구입해서 소장하고 있습니다. ^^
on lisp 원래
on lisp 원래 어렵습니다.
내공이 쌓이지 않으면 힘들죠. practical로 먼저 기본기 쌓고 ansi본다음에 on lisp보시는게 나을듯.
댓글 달기