SICP를 보면서

handrake의 이미지

요즘 SICP를 보고 있습니다. 확실히 유명한 책(?)이라 그런지 내용도 알차고 좋은데요
(다만 신입생을 위해 쓰여졌다는 것은 살짝 오버같은 느낌이... 역시 MIT?)
여기 나오는 코드를 자세히 보면 거의 다가 재귀(recursion)를 이용해서 짜여져 있다는
것을 알 수 있습니다. 요즘 또 느끼고 있는게 바로 이 재귀의 오묘함인데요, 짧은
코드로 아주 간단하게 쓰여진 함수 하나가 모든 Tree를 다 돌면서 검색하거나 처리하는
것을 보고 참 대단하구나 느낍니다. 전에 스도쿠 푸는 문제를 혼자 생각해 보다가 결국은
Backtracking으로 풀 수 밖에 없다는 것을 깨닫고 계속 고민해 보았는데요, Backtracking은
또 recursion으로 연결된다는 것을 알았습니다. 아주 두꺼운 책도 아니면서 입문(?)에 필요한
내용은 다 담은 것 같아 정말 CS의 명저라 불릴만 한 것 같습니다.

댓글

Bini의 이미지

개인적으로 이책은 초반부를 넘기는게 관건인것 같습니다.
이제 반정도를 본것같은데 보다가 그만두기를 몇번한것 같네요.
처음보시는 분이 여기계시다면,
많은 분들이 이미 언급하셨듯이 연습문제는 아주 훌륭하지만
너무 연연하는건 포기하는 지름길일수도 있다는 생각이 듭니다.
오히려 좀 가벼운 마음으로 읽으시는게...
함수형언어를 처음 접하는 분들에게는 좀 까다로울수도 있고...

스킴이라는 언어에 대해서 꽤 관심이 가는데 아쉬운건 개발환경이 좀 그렇네요.
그래픽과 관련된 프로그래밍을 주로하는데 가장 알려진 Plt-Scheme 은 GUI 쪽이 상당히 불안하고 속도도 별로구요.
리습쪽도 마찬가지라는 느낌이... 이건 이맥스 아니면 도대체가...
웹과 관련된 프로그래밍이라면 궁합이 잘 맞을지도... ^^
그냥 저의 사견입니다.

handrake의 이미지

연습문제보다는 일독을 먼저 하는 것을 목표로 잡고 보고 있습니다.
저도 Scheme과 Common Lisp에 대해 참 아쉬운게 파이썬이나 펄 같이
Library가 풍부하지 않다는 점입니다. 개인이 관리하는게 있긴 한데
보통 업데이트가 안된지 몇 년은 된 것들이 많고요... 이 것만 해결되면
정말 쓸 곳이 많을 것 같은데요.

gurugio의 이미지

이 책때문에 scheme을 보다가 불만스러워서 Common Lisp을 보고있습니다.
어느정도 문법을 익히고 다시 이 책을 보려고 합니다만...뭐 그때되면 알겠지요 ;-)

----
섬기며 사랑하면 더 행복해집니다.
몸에 좋은 칼슘이 듬뿍담긴 OS 프로젝트 - 칼슘OS http://asmlove.co.kr/wiki/wiki.php/gurugio

나빌레라의 이미지

저는 재귀 비판론자입니다.

사실 제가 재귀를 싫어하는건 재귀를 잘 이해 못해서가 가장 큰 이유입니다만,
재귀로 작성할 수 있는 모든 코드는 반복문으로 작성할 수 있다는 경험과 믿음 때문이기도 하지요.

그래서 어떤 알고리즘을 생각할 때 재귀로 작성하려는 시도 자체를 안하는데요,

그러다 보니 Erlang을 공부할 때 정말 힘들더군요.

작성된 코드를 보면 이해가 되는데, 막상 제가 어떤 코드를 Erlang을 이용해서 작성하려고 하니
당최 코드가 나오질 않더라구요.

Erlang 처럼 언어 자체에서 재귀를 필요로 하는 함수형 언어같은 것을 이해하려면 재귀에 대한 이해는 반드시 선행되어야 하겠더라구요.

더구나 저같은 재귀 비판론자는 심연의 깊은곳에서 부터 뿜어져 나오는 강한 반감(?)을 이겨내는 정신적 노력도 필요합니다..^^

----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라

----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라

winner의 이미지

저도 몇번의 시도는 해본 바 있고, 성능의 항상을 경험해본바 있지만 결론은 일반화시킬 수가 없다는 것이었습니다.
그런 연구도 있는 것으로 들었습니다만 가능한건지 의문이군요.

예를 들어 하노이의 탑부터 어떻게 반복으로 작성할까요? 이재규씨의 'C로 배우는 알고리즘'에 C로 작성된 code가 있긴 합니다. 하지만 일반화가 가능하냐는 것에 대한 대답은 없더군요.

저 역시 재귀를 대단히 어려워했고, 여전히 쉽지 않게 여기고 있습니다만 제 생각에 그 이유는 재귀를 쓸 수 밖에 없는 상황이 매우 어려운 상황이기 때문에 벌어지는 문제가 아닐까 합니다. 반복과 전역변수로 잘 하던 작업을 재귀로 고쳐가는 상황이라면 정말 어렵기 그지 없지요. 차라리 처음부터 재귀가 활용되는 형태에 익숙하고, 그대로 적용했다면 여전히 어렵긴 하겠지만 보다 편하게 작업했을텐데도요.

요새 들어 생각하는 바는 재귀를 처음부터 그렇게 어려운 상황이 아닌 곳에서 써가면서 익숙해졌다면 그렇게 어렵다는 편견을 가지지는 않았을 것이다라는 것입니다.

하지만 나빌레라님이 embedded에서 전문적으로 일하신 것으로 보이기에 나빌레라님의 생각이 잘못되었다고 보지는 않습니다.

johan의 이미지

일부 제 이야기가 있는 듯 해서 ... :-)

전 재귀를 좀 남용(?) 합니다. 재귀가 너무 익숙해서 어떤 때는 재귀로 한번 써보고 단순반복으로 바꾸려고 노력합니다.

Tail recursion되면 수행속도나 스택은 큰 문제가 안되는 경우가 대부분이지만, 단순반복으로 바꾸면 복잡한 경우가 종종 있더군요.

그냥 재귀도 잘 알고 단순반복도 잘 알아서 필요한 곳에 필요한 만큼 사용하는 것이 답인것 같습니다.

참고로 Scheme 입문서 중에 Little Schemer, Seasoned Schemer라는 얇고 그림많고 활자 큰(맞나?) 책들이 있는데, 한 두어달 가량이면 완독할 수 있고, 마치 작은 퀴즈모음집 같아서 흥미를 잃지 않을 수 있습니다(물론, 사람마다 다를 수 있습니다만). 처음부터 끝까지 재귀이야기만 나오는 재귀 특별 코스입니다. 이 코스를 마치고 나면, 왠지 단순 반복문을 쓰면 죄를 짓는 듯한 강박관념이 생겨서 반복문을 사용하는 습관을 다시 들여야 균형잡힌 프로그래밍을 할 수 있습니다.

임베디드이면 재귀 스택 오버플로우 쉽게 일어날 가능성이 있어서 간단한 것 이외에는 가능하면 안쓰는 것이 좋을 것 같은 생각이 드네요.

gurugio의 이미지

저는 땜쟁이? 시절 스택/힙 크기때문에 디어본 경험이 있어서
지금 서버에서 작업하는데도 재귀를 잊어먹고 지냅니다.
사람 생각의 습관이 고치기 힘들다는데 큰일이랑께요.
그 책 소개해주셔서 감사합니다. 저에게 꼭 필요한 책 같습니다.

----
섬기며 사랑하면 더 행복해집니다.
몸에 좋은 칼슘이 듬뿍담긴 OS 프로젝트 - 칼슘OS http://asmlove.co.kr/wiki/wiki.php/gurugio

나빌레라의 이미지

물론 하노이 탑 문제 같은건 반복문으로 만들기 힘들겠죠(불가능할지도..)

제가 저 글을 쓴 의도는

"나는 재귀를 잘 못하기 때문에 비판론자다"

라는 지극히 비 논리적인 주관을 쓴겁니다. 쉽게 말해 "나는 수학을 못해서 수학을 싫어해"와 같은 논리라는 거죠.

"모든 재귀는 반복문으로 변경가능하다"라고 한것이 아니라 "가능하다는 믿음"을 가지고 있다는 거죠..

믿음은 언제든 깨어질 수 있답니다...

또한 저는 재귀에 편견을 가지고 있지도 않습니다.
재귀로 밖에 답이 안나오는 상황에선 재귀로 코드를 작성하겠지요.

다만 왠만하면 반복문만 쓰다보니 Erlang 같은거 할때 어렵드라~~ 라는 경험을 쓴거랍니다..

제가 글을 모호하게 써서 winner님의 심기를 불편하게 해 드린것 같습니다.

죄송합니다.

----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라

----------------------
얇은 사 하이얀 고깔은 고이 접어서 나빌레라

winner의 이미지

저도 한때 멋모르고 뻘짓했던 그때의 해답이 나오지 않을까라는 생각에... 꼭 그 해답을 얻고자 여쭤본 거였습니다.
그런데 제 말투가 좀 안 좋은가보네요.
전 여쭤본다는 생각이었는데 심기가 불편한 것 같다라는 느낌을 받으신 걸 보면.... 고쳐야 할 듯.

M.W.Park의 이미지

저와는 반대 상황이시군요. ^^;
recursion을 사용하건 안하건 동일한 결과를 낼 수 있는 것은 맞지만, 제경우에는 recursion을 사용하지 않은 코드는 직관적이지 않고 별로 아름답지도 않아서 가능한한 recursion을 사용합니다.

마찬가지 이유로 recursion을 쓰기 편한 함수형 언어들(CL, Erlang)을 선호합니다.

recursion에 너무 반감을 가지지는 마세요.
함수형 언어 진영에서는 recursion이야말로 인간의 생각(알고리즘)을 모델링하는 가장 적합한 방법이라고 주장하는 사람들이 있습니다(출처 불분명).

-----
오늘 의 취미는 끝없는, 끝없는 인내다. 1973 法頂

-----
오늘 의 취미는 끝없는, 끝없는 인내다. 1973 法頂

imyejin의 이미지

되돌기를 먼저 가르치면 어떻게 되는지 보여주는 강연이 있습니다. 되돌기를 먼저 가르치고 함수를 먼저 가르쳤더니 대입과 반복문을 가르치자 아이들이 왜 이런 걸 만들었냐며 큰 반감을 표출했다고 하는 내용을 포함하고 있습니다. 함수와 되돌기를 가르치는 것은 중고등학교 학교 수학 교육과정과도 잘 들어맞습니다. 자연수를 배우고 함수와 수열을 배울 때 되돌기의 개념을 이해하는 것은 필연적이거든요. 저같은 경우는 프로그래밍을 배울 때 대입이라는 개념에 거부감이 강하게 들었습니다. x = x + 1 이라는 C 코드를 보고 저런 말도 안되는 식을 왜 쓸까라는 의문을 프로그래밍 배울 때 한번쯤 품어 보지 않으셨나요 다들? 그래서 저는 개인적으로 함수와 되돌기를 제대로 사용하는 언어를 배웠을 때 모든 것이 다시 순리대로 돌아가는 평온함을 얻었습니다.

이 강연을 하는 분은 바로 How to Design Programs http://www.htdp.org/ 의 저자이기도 한데, 프로그래밍 교육이 어떻게 이루어져야 하는지 진지하게 고민하며 10년 이상 대학교/고등학교/중학교에 이르기까지 프로그래밍 교육 프로젝트를 꾸준히 진행한 경험을 바탕으로 발표한 강연입니다. 대략 이런 실제 교육현장에서 10여년의 경험을 바탕으로 하는 강연이기 때문에 재귀는 사람에게 부자연스러운 생각이다 이렇게 관념적으로 주장하시던 분들도 "내가 직접 해봤다는데 어쩔?"이라는 포쓰 앞에서는 다시 한번 생각해 보실 기회를 갖게 되리라 생각합니다.

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

Bini의 이미지

혹시 스킴에 관심이 있으시다면 -> http://www.scheme.com/tspl4/
스킴문법이 워낙단순해서 그렇게 어렵지 않습니다.
저도 간간히 재미삼아 보는데 예제코드의 질이 좋아보이네요.
최근에 나온 네번째판입니다.

handrake의 이미지

감사합니다. 한번 시간 내서 읽어봐야 겠네요.

NoSyu의 이미지

c'est un des orgueils de notre pauvre humanité, que chaque homme se croie plus malheureux qu'un autre malheureux qui pleure et qui gémit à côté de lui
- Le Comte de Monte-Cristo
-----------------------------------------------------------------------

C를 먼저 배워서(정확하게는 BASIC이지만...)인지 반복문을 쓰면 될 것을 재귀문으로 쓰려니 참으로 힘들었습니다.

그래도 결국 같은 일을 한다는 점이 놀랍게 느껴졌던 기억이 납니다.

번외의 얘기이지만, 전 재귀보다 더 놀라운 것이 reference model이었습니다.

변수에 값을 할당하는 것이 아니라 실제 value를 가리키는 것만 할 뿐이라는 것입니다.

물론 뒤에 set 함수를 써서 할당하는 것처럼 하였지만(실제 implementation에서는 어떻게 하는지 모르겠네요.) 연습문제를 풀면서 그 점이 가장 힘들고 새롭게 느껴졌던 기억이 있습니다.

c'est un des orgueils de notre pauvre humanit?, que chaque homme se croie plus malheureux qu'un autre malheureux qui pleure et qui g?mit ? c?t? de lui
- Le Comte de Monte-Cristo
-----------------------------------------------------------------------

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.