Lisp 에서 tail recursion 질문입니다.

azura4의 이미지

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 이 맞는지, 어떻게 그렇게 이해할 수 있는지 조언 부탁드립니다. 꾸벅

(들여쓰기가 안되서 점으로... ㅡㅡ;)

winner의 이미지

Tail recursion 을 모르는 것은 아닙니다만 단지 반환값의 사용여부만 가지고 판단할 수는 없습니다.
물론 번역기가 반복형식으로 전환하기는 어렵겠습니다만 흔히 작성되는 계승함수는
반환값을 사용합니다만 꼬리재귀라고 볼 수 있다고 생각합니다.
이 경우는 진입을 할 때 아무런 작업없이 진입을 하니까 가능하겠죠.

즉 진입전에만 작업하거나 혹은 탈출 후에만 작업이 이루어진다면 비대칭으로서 꼬리재귀라고 생각합니다.

또한 역시 흔히 작성되는 Quick Sort 의 경우 반환값을 사용하지 않습니다만 꼬리재귀라고 말할 수 없겠죠.

cinsk의 이미지

안쪽 (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/

jj의 이미지

practical common lisp도 졸트어워드에 빛나는 좋은 책이더군요! 물론 웹에서 볼 수 있음
http://www.gigamonkeys.com/book/
--
콘쏠의힘

--
Life is short. damn short...

azura4-의 이미지

이전에 C++ 쓸 때는 거의 쓰지 않아서 그런지 recursion에 익숙하지 않아서...

진도가 잘 안나가네요 휴..

그리고 책 추천 감사합니다. 좋은 책이어서 구입해서 소장하고 있습니다. ^^

익명사용자의 이미지

on lisp 원래 어렵습니다.

내공이 쌓이지 않으면 힘들죠. practical로 먼저 기본기 쌓고 ansi본다음에 on lisp보시는게 나을듯.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.